Page 16 - 4800

ЛАБОРАТОРНА РОБОТА № 2
КЕРУВАННЯ ХОДОМ ВИКОНАННЯ ПРОГРАМ У СИСТЕМІ
ПРОЛОГ

Мета роботи: познайомитися з процесами уніфікації і пошуку з поверненням, з
методом відкату після невдачі та дією предикатів невдачі (fail) і відсікання (cut).
Вивчити правила уніфікації термів, методи організації повторного виконання групи
задач. Навчитися будувати меню.

2.1 Робота системи Пролог при виконанні запитів

Запит до системи – це завжди послідовність, що складається з однієї або
декількох цілей. Для відповіді на запит система намагається досягти всіх цілей, тобто
показати, що твердження, що міститься в запиті, істинні в припущенні, що всі
відношення в програмі істинні. Іншими словами, досягти мети – це показати, що вона
логічно випливає з фактів і правил програми, а якщо в запиті є змінні, то ще і
конкретизувати їх, тобто знайти ті конкретні об'єкти, при підстановці яких замість
змінних, забезпечать досягнення мети.
Для цього система заглиблюється в структуру програми так глибоко, як це
необхідно, щоб знайти факти, що необхідні для доказу істинності запиту. Потім
система повернеться у вихідний стан, довівши або виявивши, що не в змозі довести,
істинність запиту. В основі роботи системи лежить рекурсивний циклічний процес
уніфікації (тобто зіставлення зі зразком) і доведення підцілей.
При надходженні запиту система переглядає всю програму в пошуках першої
пропозиції, заголовок якої буде уніфікуватися з запитом. Для того, щоб запит і
заголовок пропозиції уніфікувалися між собою, необхідно:
– збіг у них імені предиката;
– збіг кількості аргументів предиката;
– можливість уніфікації всіх аргументів предиката (правила уніфікації термів
приведені нижче).
Якщо було виявлено пропозицію, що уніфікується з запитом, то вона починає
оброблятися:
– якщо тіло пропозиції є порожнім (тобто це факт), то запит відразу виявляється
успішним, змінні запиту конкретизуються об'єктами факту, і це рішення позначається
покажчиком повернення;
– якщо тіло пропозиції містить підцілі, то, послідовно зліва на право, кожна з
них обробляється так само, як вихідний запит.
Якщо система в тексті програми не знаходить пропозиції, що уніфікується з
запитом, то вона:
– повернеться до останньої успішно доведеної підцілі;
– ліквідує конкретизацію всіх змінних, що були результатом успішної обробки
цієї підцілі, тобто робить змінні знову вільними;
– приступає до пошуку в множині пропозицій поточної програми, заголовка
іншої пропозиції, що уніфікується з даною підціллю.
Така процедура обробки запиту одержала назву пошук з поверненням.
Застосовуючи її, при успішному виконанні запиту система видає:
– або значення всіх змінних, що входять до складу запиту;
– або слова “так” або “ні”, якщо змінні в запиті були відсутні.

2.2 Уніфікація термів

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

16