« Назад

Мета: ознайомитися з процесом повторення: цикли та рекурсивні процедури.

Хід роботи

Загальні відомості

Visual Prolog не має конструкцій FOR, WHILE, REPEAT. Не існує прямого способу вираження повтору. Пролог забезпечує тільки два види повторення - відкат, за допомогою якого здійснюється пошук багатьох рішень в одному запиті, і рекурсію, у якій процедура викликає сама себе. Visual Prolog розпізнає спеціальний випадок рекурсії - хвостову рекурсію - і компілює її в оптимізовану ітераційну петлю.

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

Використання відкату з петлями

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

repeat().

repeat():-repeat().

Цей прийом демонструє створення структури управління Прологу (лістинг програми з прикладу 1), яка породжує нескінченну безліч рішень. Мета предиката repeat() - допустити нескінченність пошуку з поверненням (нескінченну кількість відкатів).

Приклад 1 - Використання відкату з петлями

Використання repeat для збереження введених символів і друкувати їх до тих пір, поки користувач не натисне Enter (Введення).

Лістинг програми

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

Дана програма показує, як працює repeat. Правило typewriter:- описує процес прийому символів з клавіатури і відображення їх на екрані, поки користувач не натисне клавішу <Enter>.

Правило typewriter працює таким чином:

1. Виконує repeat (який нічого не робить, але ставить крапку відкату).

2. Привласнює змінній C значення символу.

3. Відображає C.

4. Перевіряє, чи відповідає C коду повернення каретки ("/ n").

5. Якщо відповідає, то - завершення. Якщо ні - повертається до точки відкату і шукає альтернативи. Так як ні write, ні readChar не є альтернативами, постійно відбувається повернення до repeat, який завжди має альтернативні рішення.

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

Увага:

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

 

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

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

Наприклад, необхідно знайти факторіал числа N: якщо N дорівнює 1, то факторіал дорівнює 1, інакше знайти факторіал N-1 і помножити його на N.

Щоб знайти факторіал 3, ви повинні знайти факторіал 2, а щоб знайти факторіал 2, ви повинні обчислити факторіал 1. Ви можете знайти факторіал 1 без звернення до інших факторіалів, тому повторення не почнуться. Якщо у вас є факторіал 1, то множите його на 2, щоб отримати факторіал 2, а потім множите отримане на 3, щоб отримати факторіал 3.

У Visual Prolog це виглядає так:

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

Приклад 2 - Рекурсивна процедура

Наступна рекурсивна програма обчислює факторіали. Рекурсія звичайна, не хвостова.

Лістинг програми

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

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

Інформація зберігається в області пам'яті, так званої стековим фреймом (stack frame) або просто стеком (stack), який створюється кожного разу при виклиці правила. Коли виконання правила завершується, зайнята його стековим фреймом пам'ять звільняється (якщо це не недетермінований відкат), і виконання триває в стековому фреймі правила-батька.

 

Переваги рекурсії

Рекурсія має три основні переваги:

- вона може виражати алгоритми, які не можна зручно виразити ніяким іншим чином;

- вона логічно простіша методу ітерації;

- вона широко використовується в обробці списків.

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

 

Оптимізація хвостової рекурсії

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

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

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

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

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

 

Як задати хвостову рекурсію.

Мовою Пролог фраза "одна процедура викликає іншу, виконуючи свій самий останній крок"означає:

- виклик є самою останньою підціллю пропозиції;

- раніше в пропозиції не було точок повернення.

Нижче наводиться приклад, що задовольняє обом умовам:

Ця процедура є хвостовою рекурсією, яка викликає себе без резервування нового стекового фрейму, і тому не виснажує запас пам'яті. Як показує програма (лістинг програми з прикладу 3), якщо ви дасте їй цільове твердження count(0), то предикат count буде друкувати цілі числа, починаючи з 0, і ніколи не зупиниться. У кінцевому рахунку відбудеться цілочисельне переповнення, але зупинки через виснаження пам'яті не відбудеться.

Приклад 3 - Хвостова рекурсія

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

Лістинг програми

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

 

Неоптимізована хвостова рекурсія

Помилковий спосіб організації хвостової рекурсії. Якщо рекурсивний виклик - не самий останній крок, процедура не є хвостовою рекурсією. Наприклад:

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

Приклад 4 - Неоптимізована хвостова рекурсія

У даній програмі наведені версії badcount1(badcount2, badcount3), які використовують хвостову рекурсію.

Лістинг програми

Рис. 4 Результат выполнения программы из примера 4

 

Використання аргументів в якості змінних циклу

Здійснимо невелике перетворення з Pascal на Пролог. У розділі "Рекурсивні процедури" ми показали обчислення факторіала за допомогою рекурсивної процедури. Тут ми використовуємо для цього ітерацію. В Pascal це виглядало б так:

Оператор := є оператором присвоювання і вимовляється як "привласнити". Тут 4 змінних. N - число, факторіал якого буде обчислюватися; FactN - результат обчислення; I - циклічна змінна, змінювана від 1 до N, P - сумуюча змінна.

Перший крок в перекладі на Пролог - заміна for більш простим формулюванням для циклу, точніше визначальною, що відбувається з I на кожному кроці. Використовуємо для цього визначення while:Р : = 1; / * Ініціалізація Р і I * /

Програма (лістинг програми з прикладу 5) показує перекладений на Пролог цикл while мови Pascal.

Приклад 5 - Обчислення факторіала

Дана програма обчислює факторіал.

Лістинг програми

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

Розглянемо програму більш детально.

У пропозиції для предиката factorial є тільки два аргументи - N і FactN. Вони є як би входом і виходом, якщо дивитися з точки зору того, хто обчислює факторіал. Пропозиції для factoriai_aux(N, FactN, I, P) фактично забезпечують рекурсію. Їх аргументами є чотири змінні, які повинні передаватися з одного кроку в інший. Тому factorial просто викликає factorial_aux, передаючи йому N і FactN з початковими значеннями для I і P:

Так I і P ініціалізуються.

Але як factorial передає FactN, адже у неї поки немає ще значення? Відповідь полягає в тому, що концептуально Visual Prolog тут уніфікує змінну, названу FactN в одному реченні, із змінною, названою FactN в іншому реченні. Таким же чином factoriai_aux передає собі FactN в якості аргументу в рекурсивному виклику. У кінцевому рахунку остання FactN отримає значення, і після цього всі інші FactN, які уніфіковувались з нею, отримають таке ж значення. "Концептуально", так як реально є лише одна FactN. Visual Prolog може визначити з початкового коду, що FactN в дійсності не використовується перед другим реченням factorial_aux, а весь час передається одна і та ж FactN.

Тепер про роботу factorial_aux. Зазвичай цей предикат перевіряє пропозицію "I менше або дорівнює N" для циклічного обчислення, а потім рекурсивно викликає себе з новими значеннями для I і P. Тут проявляється ще одна особливість Visual Prolog. У Пролозі вірний для арифметики вираз

P = P + 1

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

Увага:

Ви не можете змінити значення змінної в Visual Prolog. У Пролозі це так само абсурдно, як і в алгебрі. Замість цього ви повинні створити нову змінну і надати їй потрібне значення. Наприклад:

Як і у випадку badcount2, в цьому реченні відсікання буде забезпечувати оптимізацію хвостовій рекурсії, хоча воно і не є останньою пропозицією в предикаті. У кінцевому рахунку I буде перевищувати N; поточні значення P і FactN уніфікуються і рекурсія припиниться. Це реалізується у другому реченні, яке виконається, коли перевірка I <= N в першому реченні буде неуспішна.

Тут немає необхідності робити FactN = P окремим кроком; уніфікація може відбуватися у списку аргументів. Підстановка однакової назви змінних вимагає, щоб аргументи на цих позиціях були рівні. Більш того, перевірка I> N надлишкова, так як зворотне було перевірено в першому реченні. Це дає завершальна пропозиція:

factorial_aux(_, FactN, _, FactN).

Завдання

1. Написати програму обчислення суми арифметичної прогресії з використанням рекурсії:

- Програма повинна робити обчислення ряду від меншого члена прогресії до більшого.

- Програма повинна робити обчислення від більшого члена до меншого.

- Оптимізовувати програми з використанням оператора відсікання.

2. Написати програму обчислення суми зростаючій геометричній прогресії з використанням рекурсії:

- Програма повинна робити обчислення ряду від меншого члена прогресії до більшого.

- Програма повинна робити обчислення від більшого члена до меншого.

- Оптимізовувати програми з використанням оператора відсікання.

3. Написати програму обчислення суми спадної геометричної прогресії з використанням рекурсії:

- Програма повинна робити обчислення ряду від меншого члена прогресії до більшого.

- Програма повинна робити обчислення від більшого члена до меншого.

- Оптимізовувати програми з використанням оператора відсікання.

4. Написати програму обчислення факторіала натурального числа:

- Програма повинна робити обчислення з зростанням ряду.

- Програма повинна робити обчислення з убуванням ряду.

- Оптимізовувати програми з використанням оператора відсікання.

Контрольні питання

1. Яким способом Пролог здійснює повтори?

2. Що таке рекурсивна процедура?

3. Що називається стековим фреймом?

4. Перелічіть переваги рекурсії.

5. Назвіть недолік рекурсії.

6. Назвіть переваги хвостової рекурсії.

Зміст звіту:

- титульний аркуш;

- мета роботи;

- основні розділи програми на мові Visual Prolog;

- лістинг програми;

- результат виконання.