2.4. Предикати введення – виведення

Серед предикатів введення і виведення найчастіше використовують такі:

• readchar (CHAR CharVariable) – зчитує з клавіатури один символ;

• readint(INTEGER IntegerVariable) – зчитує з клавіатури ціле число;

• readln(STRING StringVariable) – зчитує з клавіатури рядок символів;

• readreal(REAL RealVariable) – зчитує з клавіатури дійсне число;

• readterm(<domainName>, <TERM> Term) – зчитує з клавіатури терм певного домену;

• nl – забезпечує перехід на наступний рядок;

• write(e_1, e_2, e_3, … , e_N) – виводить декілька аргументів на екран;

• writef(STRING FormatString, Arg1, Arg2, Arg3, … ) – здійснює форматоване виведення аргументів на екран (аналог функції printf() у мові Сі).

З іншими предикатами введення/виведення можна ознайомитись у розділі Input/Output standard predicates довідки Visual Prolog.

2.5. Об’єкти даних

Об’єкти даних можуть бути простими та складними (або структурами). Прості дані – це змінні і константи. Константа може бути символьною (char), числовою (integer, real) або атомарною (symbol, string).

Складні об’єкти (далі – структури) – це об’єкти, які складаються із декількох компонент. Ці компоненти також можуть бути структурами. Наприклад, дату можна розглядати як структуру, що складається з трьох компонентів: день, місяць та рік. Для об’єднання цих компонентів у структуру треба вибрати так званий функтор – ім'я складного об'єкта. У розглядуваному випадку можна використати функтор data:

date(1, april, 2000).

Структури можна зображати у вигляді дерев. Корінь дерева – це функтор, а гілки – компоненти. Якщо компонент являє собою структуру, то його можна зобразити у вигляді піддерева. Наприклад, якщо об’єкт – комп’ютер, то він становить сукупність таких компонент, як процесор, обсяг оперативної пам’яті й монітор, у свою чергу процесор включає тип, тактову частоту, обсяг кеш-пам’яті. Структуру computer(processor(Pentium – 4, 3.0, 1024 ), 512, Samsung 913N) можна зобразити у вигляді дерева, показаного на рис. 7.

computer

/ | \

processor 512 Samsung 913N

/ | \

Pentium 4 3.0 1024

Рис.7. Структура computer, подана як дерево

Завдання 1

Використовуючи предикати parent(string parent, string son-daughter), women(symbol) і man(symbol), розробити предикати, що визначають такі поняття:

1. Правнучка.

2. Двоюрідний брат.

3. Внук.

4. Дівер.

5. Зять.

6. Тесть.

7. Свекруха.

8. Теща.

9. Свекор.

10. Прадід.

11. Племінник.

12. Прабабуся.

13. Племінниця.

14. Свояк.

15. Тітка.

16. Своячка.

17. Дядько.

18. Дідусь.

19. Правнук.

20. Внучка.

21. Бабуся.

Написати програму для пошуку й виведення на екран інформації про відповідного родича в БД.

2.6. Вбудовані механізми мови Пролог. Керування бектрекінгом

В основі роботи Пролог-системи лежить два механізми – уніфікація та бектрекінг. Уніфікація – це процес перевірки на збіг двох об’єктів і конкретизація вільних змінних. Правила уніфікації такі:

1. Якщо два об’єкти – константи, то їх можна уніфікувати, якщо вони становлять один і той же об’єкт.

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

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

Наведемо приклади об’єктів, які можна уніфікувати: константи 2 і 2, ‘s’ і ‘s’; змінна X і структура data(12, May, 2004), у результаті змінній X буде присвоєне значення data(12, May, 2004); можна уніфікувати структури data(X, Y, 2004) та data(12, May, 2004), у результаті змінним X i Y будуть присвоєні значення 12 і May.

Бектрекінг – це механізм циклічного рекурсивного повернення для знаходження додаткових фактів і правил, необхідних для досягнення цілі, якщо поточна спроба її досягнення виявилася невдалою.

Таким чином, роботу Пролог-системи можна розглядати як рекурсивний циклічний процес уніфікації та досягнення підцілей.

Наведемо для пояснення такий приклад.

domains

parent = symbol

son_daughter = symbol

facts

parent(parent, son_daughter)

women(symbol)

man(symbol)

predicates

nondeterm son_daughter(son_daughter, parent)

clauses

parent(pam, bob).

parent(bob, ann).

women(pam).

women(ann).

man(bob).

son_daughter(X, Y):- parent(Y, X), man(X).

son_daughter(X, Y):- parent(Y, X), women(X).

goal

son_daughter(ann, bob).

Пролог-системі поставлено запитання, чи є Анн дочкою або сином Боба: son-daughter(ann, bob). Пролог-система починає з цілі й застосовуючи правила, замінює поточні цілі новими, допоки ці нові цілі не стануть простими фактами. Спочатку Пролог-система шукає таке речення в програмі, голову якого можна уніфікувати з ціллю, тобто із son-daughter(ann, bob). Такими реченнями є два речення, стосовні предиката son-daughter.

Спочатку Пролог-система вибирає речення, яке стоїть у програмі першим:

son-daughter(X, Y):- parent(Y, X), man(X).

Після уніфікації структур son-daughter(ann, bob) та son-daughter(X, Y) значення змінних будуть X=ann, Y=bob. Тоді початкова ціль буде замінена двома новими: parent(bob, ann) і man(ann). Перша з них досяжна, оскільки її можна уніфікувати з фактом із програми, друга не досяжна – її не можна уніфікувати з жодним фактом чи правилом програми. Ціль man(ann) є неуспішна.

Тепер Пролог-система повертається до початкової цілі son-daughter(ann, bob) (бектрекінг), щоб реалізувати другий варіант виведення цілі, тобто

son-daughter(X, Y):- parent(Y, X), women(X).

Аналогічно Пролог-система приходить до двох цілей: parent(bob, ann) і women(ann). Оскільки обидві цілі можна уніфікувати з фактами програми, вони досяжні. Таким чином, запит до Пролог-системи є успішний, і вона дасть позитивну відповідь: yes.

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

Розглянемо, наприклад, таку функцію:

якщо Х < 2, то Y = 10;

якщо Х ≥ 2 i Х < 4, то Y = 20;

якщо Х ≥ 4, то Y = 30.

Мовою Пролог цю функцію можна реалізувати таким чином:

f(X, 10) :- X < 2.

f(X, 20) :- X >= 2, X < 4.

f(X, 30) :- X >= 4.

Якщо тепер зробити Пролог-системі запит f(0, Y), Y=5, то після досягнення першої підцілі f(0, Y) за першим правилом f(X, 10) :- X < 2. змінна Y буде конкретизована значенням 10. Друга підціль Y=5 буде хибною, оскільки 10 не дорівнює 5. Запуститься механізм бектрекінгу, Пролог-система знову повернеться до підцілі f(0, Y) і невдало намагатиметься задовольнити її за другим і третім правилами f(X, 20) :- X >= 2, X < 4. , f(X, 30) :- X >= 4. Зрештою запит f(0, Y), Y=5 закінчиться невдало (результат – No). У ході аналізу роботи програми можна виявити, що намагання Пролог-системи задовольнити підціль f(0, Y) за другим і третім правилами даремні, тому що всі три правила взаємовиключні (якщо виконується перше правило, інші два виконуватися не будуть; X не може одночасно бути меншим за 2 і більшим або рівним 2 і т. д.). Тому в цьому випадку бектрекінг не має сенсу, і його можна заборонити таким чином:

f(X, 10) :- X < 2, !.

f(X, 20) :- X >= 2, X < 4, !.

f(X, 30) :- X >= 4.

Тепер у випадку запиту f(0, Y), Y=5, після того як за першим правилом змінна Y буде конкретизована значенням 10, а потім підціль Y=5 виявиться хибною, Пролог-система не зможе повернутися далі точки, поміченої в програмі предикатом !. Пролог-система зразу видасть результат запиту (як і в першому варіанті програми – No), не включаючи в роботу даремно друге і третє правила, що підвищить швидкість виконання програми. На декларативний зміст програми введення предиката ! не вплинуло, змінився тільки процедурний зміст, тому результати запитів до програми не зміняться, якщо вилучити предикати ! з програми.

Якщо застосування предиката ! не впливає на декларативний зміст програми, то його називають „зелений cut”, у протилежному випадку – „червоний cut”. Фахівці рекомендують конструювати програми таким чином, щоб не використовувати „червоний cut” (або використовувати якомога менше).