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

 

Запит до системи – це завжди послідовність, що складається з однієї або декількох цілей. Для відповіді на запит система намагається досягти всіх цілей, тобто показати, що твердження, що міститься в запиті, істинні в припущенні, що всі відношення в програмі істинні. Іншими словами, досягти мети – це показати, що вона логічно випливає з фактів і правил програми, а якщо в запиті є змінні, то ще і конкретизувати їх, тобто знайти ті конкретні об'єкти, при підстановці яких замість змінних, забезпечать досягнення мети.

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

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

– збіг у них імені предиката;

– збіг кількості аргументів предиката;

– можливість уніфікації всіх аргументів предиката (правила уніфікації термів приведені нижче).

Якщо було виявлено пропозицію, що уніфікується з запитом, то вона починає оброблятися:

– якщо тіло пропозиції є порожнім (тобто це факт), то запит відразу виявляється успішним, змінні запиту конкретизуються об'єктами факту, і це рішення позначається покажчиком повернення;

– якщо тіло пропозиції містить підцілі, то, послідовно зліва на право, кожна з них обробляється так само, як вихідний запит.

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

– повернеться до останньої успішно доведеної підцілі;

– ліквідує конкретизацію всіх змінних, що були результатом успішної обробки цієї підцілі, тобто робить змінні знову вільними;

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

Така процедура обробки запиту одержала назву пошук з поверненням. Застосовуючи її, при успішному виконанні запиту система видає:

– або значення всіх змінних, що входять до складу запиту;

– або слова “так” або “ні”, якщо змінні в запиті були відсутні.

 

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

 

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

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).