Глава 6

Мова логічного програмування Prolog

Prolog – це найбільш відома мова логічного програмування, яка використовується для вирішення задач, в яких діють об’єкти та відношення між цими об’єктами. Програмування на мові Prolog відноситься до декларативного стилю програмування і має спільні властивості з функціональним програмуванням [3].

Теоретичною основою логічного програмування є логіка предикатів – один з розділів алгебри логіки. Логіка предикатів займається дослідженням відношень між об’єктами та доказами їхнього існування [4]. Такі відношення називаються предикатами і записуються у вигляді

P(t₁, t₂, t₃, …, t_n),

де: P – позначення предикату

t₁, t₂, t₃, …, t_n – об’єкти чи терми.

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

С Ú ˜E Ú ˜F Ú ˜G (5.1)

Фраза 5.1 означає, що С істина тоді і тільки тоді, коли E, F і G одностайно істинні. Звичайно, 5.1 можна переписати у вигляді імплікації зі зворотною стрілкою:

C E, F, G (5.2)

Така фраза є основою побудови висловлювань програми на логічної мові програмування Prolog.

Склад та структура програми

Програма на мові Prolog складається з висловлювань трьох типів: факти, правила та питання. Твердження складається з двох частин: ліва частина – висновок, права частина – умова, які розділяються знаком «:-» (двокрапка і дефіс) [1, 4].

Факт – це твердження, що є безумовною істиною, який складається з висновку за яким не виходить ніяких умов, наприклад:

лікар (василь).

Це можна прочитати так:

Василь - лікар*).

Сукупність фактів складають деякий світ, у межах якого дійсні твердження програми.

На прикладі родинних відносин (рис. 5.1) введемо відношення батьки (parent) між двома об’єктами X і Y, яке встановлює той факт, що X є батьком чи мати для Y:

parent (X, Y).

Рисунок 5.1 – Схема родинних відношень

Тоді родинні зв’язки, які зображені на рис. 5.1, запишемо у вигляді списку фактів:

parent (тетяна, ігор).
parent (ігор, сергій).
parent (ігор, ліза).
parent (сергій, ганна).
parent (сергій, петро).
parent (марина, ганна).
parent (петро, юлія).

При написанні фактів потрібно дотримуватись наступних правил:

- імена всіх відносин та об’єктів з маленької літери;

- спочатку записується ім’я відносин, потім в круглих дужках через кому об’єкти;

- в кінці ставиться крапка.

Після написання будь-якої програми та їй завантаження середовище Prolog може відповісти на запитання.

Запитання – це твердження, що містить лише умову без висновку. Запитання складається з одній або декількома цілей [2]. Якщо всі цілі досягненні, Prolog дає позитивну відповідь – Так (Yes), у протилежному випадку – негативну відповідь Ні (No). Якщо у параметрах предикатів існують зміни, тоді, при позитивній відповіді, зміни конкретизуються, тобто приймають конкретне значення (див. нижче). В таблиці 5.2 наведені приклади запитань у контексті вищевказаної програми родинних відношень.

Таблиця 5.2 – Приклади запитань
Запитання	Відповідь
? parent(сергій, ганна).	Yes
? parent(сергій, ліза).	No
? parent (сергій,X).	X = ганна; X = петро;
? parent (X, ліза).	X = сергій

 

Правила - це залежні відношення і дозволяють Prolog робити виведення, порівнюючи одну частину інформації з іншою [1, 2].

Правила Prolog складаються з обох частин твердження: висновку та умови. Іноді висновок називають головою, умови – тілом правила.

Голова - це факт, який буде вірним, якщо деяка кількість умов виконається. Тіло - це множина умов, котрі повинні бути істинними, щоб Prolog міг довести, що голова правила вірна [2].

Наприклад, введемо відношення child "дитина", зворотне до parent "батьки" і запишемо у вигляді правила:

child(Y, X):-parent (X, Y).

Правило читається так: для всіх X та Y, Y дитиною X, якщо X – батько (мати) Y.

Правило доповнює базу даних програми новою сутністю child. Зараз можна запитати:

?-child(ліза, ігор).

В базі даних програмі немає фактів child,але є правило, яке залежить від існуючих фактів parent. У даному випадку Prolog підставляє умовну частину правила замість запитання:

parent (ігор, ліза),

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

Основи мови Prolog

Програма на мові Prolog складається з речень. Речення бувають трьох видів: факти, правила, запитання. Всі речення складаються з термів [1, 2, 3].

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

f (t₁, t₂, …, t_n),

де: f - позначення функції; t₁, t₂, …, t_n - терми.

Терм записується як послідовність літер. Літери поділяються на чотири категорії: прописні букви, строкові букви, цифри, спеціальні символи такі як: + – * / \ < > ^:. ˜ &? _ @ # $.

Константами є поіменні конкретні об’єкти або конкретні відношення. Існує два види констант: атоми та числа.

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

liz

—>

=====>

міс_Джонс

міс_джонс

key5689

’микола’

’Джордж-сміт’

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

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

А

Висновок

_33

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

дата(22, травня, 2000)

Ім’я структури називається функтором, кількість параметрів – арністю. Prolog дозволяє застосування структур з однаковим функтором і різною арністю.

Відповідь на запитання і пошук рішень

Відповідь на запитання здійснюється на основі фактів і правил, з яких складається програма. Необхідно звернути увагу на те, що повнота відповіді залежить від повноти складу бази даних програми (фактів), що описують «світ» програми [4].

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

Уніфікація може бути успішною або ні. Якщо уніфікація успішна, тоді ціль досягнуто. Успіх уніфікації залежить від складу термів, які співставленні. Крім того, якщо терм є зміною або у складі терму входить зміна, в результаті уніфікації зміна може бути конкретизована (отримати значення), якщо уніфікація успішна. Prolog керується наступними правилами [3, 4]:

1) Якщо уніфікуються дві константи, тоді уніфікація є успішною, якщо обидві константи однакові.

2) Якщо уніфікуються зміна з константою або структурою, уніфікація є успішною, а зміна конкретизується значенням константи або структури.

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

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

5) Уніфікація завжди успішна, якщо терм зіставляється з анонімною зміною (підкреслення).

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

Методичні вказівки

Етапи виконання роботи

Виконання завдання складається з чотирьох етапів:

1) складання схеми зв’язків між об’єктами;

2) формулювання і запис правила з використанням квантору загальності [4];

3) запис правила на мові Prolog;

4) формулювання запитань та отримання відповідей у середовищі Prolog.

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

Приклад виконання завдання

Задача: Скласти правило для визначення предикату «донька» на основі фактів. жінка (ім’я), батьки (ім’я_батька, ім’я_дитини).

Рішення: Предикат «донька» позначимо daughter(X, Y), де X – імя доньки, Y – імя одного з батьків (мамо або тато). Базу фактів можна скласти на основі схеми родинних відношень, яка представлена на рис. 5.1. Необхідно додати ще факти, які визначать жінок:

woman(тетяна).

woman(ліза).

woman(ганна).

woman(марина).

woman(юлія).

Предикат можна сформулювати наступним чином: для всіх X і Y, X є донькою Y, якщо X є жінкою, і Y є батьком X.

Тоді, правило на мові Prolog має вигляд:

daughter(X,Y):- woman(X), parent(Y,X).

Після цього можна поставити запитання (табл. 5.3)

Таблиця 5.3 – Приклади запитань
Запитання	Пояснення	Відповідь
? daughter(ганна,марина).	Чи є Ганна донькою Марини?	Yes
? daughter(ганна, X).	Хто є батьком (мати або тато) Ганни?	X = марина; X = сергій
? daughter(X,марина).	Хто є донькою Марини?	X = ганна
? daughter(_,ліза).	Чи є у Лізи донька?	No

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

1) Визначення поняття предикату.

2) Визначення понять: факт, правило, запитання.

3) Основні визначення мови Prolog: терм, атом, константа, змінна, структура.

4) Правила уніфікації термів.

5) Поясніть, як Prolog-система дає відповідь на запитання.

Глава 6