Приклад програми на пролозі
Опис задачі у вигляді фактів і правил розміщують в секції Clauses(твердження). Факти краще записувати перед правилами, якщо інший порядок розміщення тверджень не диктується задачею. При запису фактів і правил використовують предикати користувача і стандартні предикати.
Для того, щоб Пролог розумів предикати користувача, їх описують в секції Predicates. Для кожного предиката вказують ім’я та типи аргументів аналогічно тому, як описують заголовки процедур в інших мовах. Пролог має вбудовані стандартні предикати для виконання дій. Такі, як предикати вводу-виводу, тощо. Їх не описують.
Секцію Predicates розміщують перед секцією Clauses.
Ціль вказують у секції Goal. Секція може розміщуватися як перед секцією Clauses так і після неї. Проте для написання програми краще розміщувати секцію Goal перед секцією Clauses.
Взагалі, секції розміщують за принципом: те, що використовують, описують раніше.
Напишемо програму для нашого завдання:
Predicates
father (string, string)
brother (string, string)
Clauses
father (“Дмитро”, ”Володимир”).
father (“Дмитро”, ”Олександр”).
brother (X, Y):- father (Z, X), father (Z, Y), X<>Y.
Goal
brother (X, Y), write(X, ’ ’, Y).
В програмі використано стандартні предикати: <>, write.
2.6. Виконання програми на пролозі
Виконання програми неможливо без цілі. Пролог вважає назву секції Goal стандартним предикатом і виконання програми починає з нього.
Процес доведення істинності цілі для нашої програми можна ілюструвати за допомогою дерева цілей. Де верхня ціль предикат Goal, а інші цілі поточні, що породжуються під час роботи програми.
На рисунку 2 відображено дерево цілей для вище показаної програми:
РИС.2
Програма виконується в такій послідовності:
Обирається ціль з секції Goal. Складна ціль проглядається зліва на право. Тобто спочатку доводиться істинність поточної цілі brother (X, Y) і, якщо ціль істинна, поточною ціллю стає предикат write(X,’ ‘,Y).
Пролог шукає в секції Clauses твердження, яке записано з таким же предикатом як поточна ціль з секції Goal. Пошук кожного предикату завжди проводиться від початку секції. Для цілі brother (X, Y) із секції Goal знайдеться умовне твердження brother (X, Y). Між аргументами, що стоять на відповідних місцях цілі і умовного твердження, встановлюється зв’язок. Через такий зв’язок змінні цілі одержать свої значення. Якщо буде доведено, що умовне твердження істинно, то і ціль буде істиною.
Умовне твердження буде істинним при істинних умовах. Тому з’являються три нові поточні цілі father( Z, X ), father (Z, Y) та X<>Y істинність яких треба довести. Ще до роботи програми, компілятор проставляє для кожної поточної цілі маркери на твердженнях з якими ця ціль може бути зіставлена. У прикладі дві перші цілі мають по два маркери на фактах і можуть бути зіставлені кожна з двома фактами.
Вибирається перший факт для поточної цілі father ( Z, X ). Змінна Z конкретизується значенням „Дмитро”, а змінна X конкретизується значенням „Володимир”. Витирається маркер на першому факті для цієї цілі, як для використаної.
Значення змінної Z передається в другу поточну ціль і вона прийме вид father („Дмитро”, Y). Друга поточна ціль зіставляється з першим свої фактом. Змінна Y теж конкретизується значенням „Володимир”, а маркер на першому факті витирається.
Але третя ціль X<>Y вимагає, щоб імена не були однаковими. Ця умова вводиться, щоб хлопець не був братом сам собі. В нашому випадку X=Y. Тому X<>Y буде невірним твердженням. Якщо одна з умов невірна, то і умовне твердження буде невірним.
Для пошуку іншого розв’язку включається механізм звороту. Керування передається на найближчий зліва предикат, що має декілька розв’язків. Змінна Y звільнюється і для другої цілі father („Дмитро”, Y) вибирається наступний факт
father (“Дмитро”, ”Олександр”). Змінна Y одержує нове значення „Олександр”.
В цьому випадку твердження X<>Y вірне, отже умовне твердження теж вірне. Умовне твердження істинно при X = „Володимир”, Y= „Олександр” і тому ціль brother (X, Y) з секції Goal одержує ці значення і теж вірна.
Одержані значення змінних виводяться на екран стандартним предикатом write (X, ’ ’, Y).