Робота системи Пролог при виконанні запитів
Запит до системи – це завжди послідовність, що складається з однієї або декількох цілей. Для відповіді на запит система намагається досягти всіх цілей, тобто показати, що твердження, що міститься в запиті, істинні в припущенні, що всі відношення в програмі істинні. Іншими словами, досягти мети – це показати, що вона логічно випливає з фактів і правил програми, а якщо в запиті є змінні, то ще і конкретизувати їх, тобто знайти ті конкретні об'єкти, при підстановці яких замість змінних, забезпечать досягнення мети.
Для цього система заглиблюється в структуру програми так глибоко, як це необхідно, щоб знайти факти, що необхідні для доказу істинності запиту. Потім система повернеться у вихідний стан, довівши або виявивши, що не в змозі довести, істинність запиту. В основі роботи системи лежить рекурсивний циклічний процес уніфікації (тобто зіставлення зі зразком) і доведення підцілей.
При надходженні запиту система переглядає всю програму в пошуках першої пропозиції, заголовок якої буде уніфікуватися з запитом. Для того, щоб запит і заголовок пропозиції уніфікувалися між собою, необхідно:
– збіг у них імені предиката;
– збіг кількості аргументів предиката;
– можливість уніфікації всіх аргументів предиката (правила уніфікації термів приведені нижче).
Якщо було виявлено пропозицію, що уніфікується з запитом, то вона починає оброблятися:
– якщо тіло пропозиції є порожнім (тобто це факт), то запит відразу виявляється успішним, змінні запиту конкретизуються об'єктами факту, і це рішення позначається покажчиком повернення;
– якщо тіло пропозиції містить підцілі, то, послідовно зліва на право, кожна з них обробляється так само, як вихідний запит.
Якщо система в тексті програми не знаходить пропозиції, що уніфікується з запитом, то вона:
– повернеться до останньої успішно доведеної підцілі;
– ліквідує конкретизацію всіх змінних, що були результатом успішної обробки цієї підцілі, тобто робить змінні знову вільними;
– приступає до пошуку в множині пропозицій поточної програми, заголовка іншої пропозиції, що уніфікується з даною підціллю.
Така процедура обробки запиту одержала назву пошук з поверненням. Застосовуючи її, при успішному виконанні запиту система видає:
– або значення всіх змінних, що входять до складу запиту;
– або слова “так” або “ні”, якщо змінні в запиті були відсутні.
Уніфікація термів
Найбільш важливою операцією над термами є уніфікація, при якій здійснюється конкретизація змінних, доступ до структур даних через загальний механізм узгодження і визначені типи порівнянь на рівність. Процес уніфікації відповідає передачі параметрів в інших мовах програмування. Уніфікація термів регулюється наступними правилами:
1. Вільна змінна уніфікується з константою або структурою. У результаті цього змінна стає конкретизованою, тобто приймає значення цієї константи або структури.
Goal: Х = “Іван”
Х = “Іван”
2. Змінна уніфікується із змінною, при цьому обидві вони стають однієї і тією ж змінною.
Goal: X=Y
Х=_1
Y=_1
3. Анонімна змінна уніфікується з чим завгодно.
_ = “Іван”
4. Константа може бути уніфікована з іншою константою, якщо вони ідентичні або з вільною змінною відповідного типу.
Goal: “Іван” = “Іван”
True
5. Структура уніфікується з іншою структурою за умови, що їх функтори однакові, а аргументи можуть попарно уніфікуватися.
father(X)=father(„Іван”)
X=„Іван”
Для того, щоб познайомитися з процесом уніфікації різних класів об'єктів Прологу, розглянемо виконання програмою 2.1 декількох запитів.
/* Програма 2.1 */
domains
title, author=symbol
pages=integer
publication=book(title , pages)
predicates
written_by(author, publication)
long_novel(publication)
clauses
written_by("І.Бpaтко", book("Програмування мовою Пролог", 560)).
written_by("Д.Соломон" ,book("Використання Пролога", 608)).
long_novel(book(Title, Lеngth)):- written_by(_, book(Title, Length)), Length>600.
Розглянемо запит виду: written_by(X, Y). При рішенні задачі система повинна по черзі погодити мету з пропозиціями програми, намагаючись досягти відповідності між параметрами Х і Y з однієї сторони і параметрами пропозицій програми з іншої, через операцію уніфікації.
Тому що в даному запиті змінні Х та Y є вільними і можуть узгоджуватися з будь-якою константою, то найперша ж пропозиція для предикату written_by дає бажану відповідність (рис. 2.1,а), тобто Х конкретизується константою „І.Братко”, а Y приймає значення структури book(„Програмування мовою Пролог”, 560). Система Пролог позначає цю точку покажчиком повернення і видає на екран повідомлення:
Х=„І.Братко” Y=book(„Програмування мовою Пролог”, 560)
Рисунок 2.1 – Уніфікація змінних
Оскільки ми задавали запит як зовнішню мету, система повертається в точку, позначену покажчиком повернення і продовжує, починаючи з цієї точки, процес уніфікації і знаходить другу пропозицію, що також може бути погоджена з запитом. Після уніфікації змінних система видає на екран Х =”Д.Соломон” Y=bооk(„Використання Прологу”, 608) і закінчує процес уніфікації.
Якщо введемо запит written_by(Х, book(„Використання Прологу”, Y)), то спроба уніфікації змінних з першою пропозицією програми буде виглядати так, як наведено на рис. 2.1,б.
Оскільки Х вільна, то вона набуває значення константи „І.Братко”, і робиться спроба встановити відповідність між двома структурами. Але складений об’єкт узгодиться з іншим складеним об'єктом за умови, що вони мають однаковий функтор, однакову кількість аргументів, і всі аргументи можуть бути попарно уніфіковані. Але, константа „Використання Прологу” може бути уніфікована тільки з вільної змінної або сама із собою. Оскільки між першими двома компонентами структури book відповідність неможлива, то формується ознака невдачі, і система намагається погодити мету з наступною пропозицією програми, переходячи до перевірки відповідності з наступною пропозицією (рис. 2.1,в).
Вільна змінна Х уніфікується з константою „Д.Соломон”. Обидві структури мають той самий функтор book, містять рівне число компонентів, і перші компоненти обох структур – однакові константи. Тобто, ці структури можуть бути уніфіковані, і при цьому константа 608 уніфікується із змінної Y. Тобто ціль досягнута, і Пролог виводить повідомлення:
Х = „Д.Соломон” Y = 608
Нарешті, розглянемо виконання запиту: long_novel(X). Насамперед система намагається відшукати пропозиції, заголовки яких погодяться з запитом (рис. 2.2).
Рисунок 2.2 – Уніфікація змінних при виконанні запиту long_novel(X)
Після цього узгоджуються ліва і права частини правила. Змінні Х и Title узгоджуються, тому що вони вільні і стають однієї і тієї ж змінною. Потім Пролог оголошує першу пропозицію зазначеного вище правила підзадачею і робить спробу її уніфікації (рис. 2.2,б).
Оскільки анонімна змінна узгоджується з будь-яким об’єктом і структури book також погодяться, то ці два предикати можуть бути уніфіковані. У результаті цього змінна Title набуде значення „Програмування мовою Пролог”, а змінна „Length” стає рівною 560.
Після цього робиться спроба узгодити другу підціль тіла правила, а саме: Length>600. Перед спробою уніфікації зв’язана змінна Length заміняється своїм чисельним значенням 560. Оскільки вираз: 560 > 600 хибний, то Пролог робить повернення назад до вже доведеної підцілі і намагається її передовести. Тобто знову намагається уніфікувати першу підціль written_by(_, book(Title, Length)), використовуючи наступний з наявних фактів (рис. 2.2,в), який зв'язує Title з „Використання Прологу” і Length з 608. У даному випадку виявляється: Length>600, тобто друга підціль також стає істинною. Правило цілком погоджене при отриманих значеннях змінних, задача вирішена, про що видається повідомлення:
Х=„Використання Пролога”
Вихідна мета є цілком доведеною, і робота системи Пролог закінчується.
Складний об’єкт може уніфікуватись або з простою змінною, наприклад, data(''Квітень'', 2, 1981) зрівнюється з X і зв’язує X з date(“Квітень”, 2, 1981), або ж зі складним об'єктом, який збігається з ним структурно: data(''April'', 2, 1981) порівнюється з date(Mo, Da, Yr).
Пролог проводить уніфікацію у двох місцях. По перше, уніфікація проходить, коли є виклик зіставлення голови фрази. Інший спосіб виконання уніфікації – це використання знаку (=). У цьому випадку Пролог буде ототожнювати об’єкти, які знаходяться по обидві сторони знаку. Цей підхід є корисним для знаходження значень аргументів складного об’єкта. Наприклад, наступна програма виконує такі дії. Якщо дві особи мають одне й те саме прізвище, тоді другій особі приписується адреса першої.
/* Програма 2.2 */
domains
person = person(name,address)
name = name(first,last)
address = addr(street,city)
street = street(number,street_name)
city, street_name = string
first,last = string
number = integer
goal
P1 = person(name(„Василь”,”Марків”), addr(street(5,"Бучинського"), „Івано-Франківськ”)),
P1 = person(name(_, „Марків”),Address),
P2 = person(name(„Галя”, „Марків”), Address), write(P2).