Перейти до вмісту

Пролог

Матеріал з Вікіпідручника

Вітаємо вас в вікіпідручнику мови пролог. Зауваження, коментарі, і особливо доповнення вітаються.

Вступ

[ред.]

Прологмова логічного програмування. Пролог заснований на теорії предикатів першого порядку. Назва мови програмування розшифровується як (Програмування в логіці). Ідея використання можливостей наведення теорії предикатів першого порядку — одна з головних переваг мови Пролог для комп'ютерних наук взагалі та штучного інтелекту.

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

Історія створення і розвитку мови

[ред.]

Розробка мови Prolog почалася в 1970 році Аланом Кулмерое і Філіпом Расселом. Їх метою було створення мови, який міг би робити логічні висновки на основі заданого тексту. Назва Prolog є скороченням від "Programming in logic". Отже, Prolog, як мова, був розроблений в Марселі в 1972 році. Попередньо на основі деякого "принцип резолюції" Ковальського, співробітника Единбурзького університету, була створена модель, на основі якої і був розроблений механізм логічних висновків. Перша реалізація мови Prolog з використанням компілятора Ніклауса Вірта "Algol-W" скінчилася в 1972 році, а основи сучасної мови були закладені пізніше, в 1973 р Використання мови Prolog поступово поширювалося серед тих, хто займався логічним програмуванням, в основному завдяки особистим контактам , а не через комерціалізацію продукту. В даний час існує кілька різних, але досить схожих між собою версій мови. Хоча стандарту мови Prolog не існує, проте версія, розроблена в Единбурзькому університеті, стала найбільш широко використовуваним варіантом. Тут треба відзначити той факт, що недолік розробок ефективних додатків Prolog стримував його розповсюдження аж до 1980 р

Теорія логічного програмування з часом удосконалювалася. Істотний внесок у її розвиток внесла робота Р. Ковальського "Логіка предикатів як мова програмування". У 1976 р Ковальський і М. ван Емден запропонували два підходи до прочитання текстів логічних програм - процедурний і декларативний. Обидва ці підходи стали активно використовуватися при написанні програм мовою Prolog.

Тільки в 1977 році Д. Уоррен і Ф. Перейра створюють в університеті Единбурга інтерпретатор / компілятор мови Prolog для ЕОМ DEC-10, тим самим перевівши методи логічного програмування в практичну площину. Пізніше в 1980 році К. Кларк і Ф. Маккейб у Великій Британії розробили версію Prolog для персональних ЕОМ.

Цікавий факт: в жовтні 1981 світ облетіла новина про японському проекті створення ЕОМ п'ятого покоління. В основу методології розробки програмних засобів було покладено логічне програмування. Метою проекту декларувалося створення систем обробки інформації, які базуються на знаннях, а головним засобом реалізації повинен був стати саме мова Prolog.

В цей же час (початок 1980-х років) з'являється безліч комерційних реалізацій Prolog практично для всіх типів комп'ютерів. До найбільш відомих можна віднести "CProlog", "Quintus Prolog", "Silogic Knowledge Workbench", "Prolog-2", "Arity Prolog", "Prolog-86", "Тurbo Prolog" та ін. У даній статті ми спиралися на версію мови "SWI-Prolog".

Існує думка, що Prolog - вже майже мертву мову, що він за невеликий проміжок часу (1970-1980-ті роки) зміг пройти весь життєвий цикл - від початкових розробок, стрімкого підвищення інтересу з боку вузьких спеціалістів, потім стрімкий злет популярності, падіння інтересу і майже повне забуття. Думка викликано тим, що така доля - звичайне явище в світі інформаційних технологій, де нові, досконаліші, дидактично вірні і теоретично красивіші мови програмування виникають щороку і тихо вмирають. Прихильники думки аргументують його тим, що структура Prolog-програм дуже важка до через те, що іноді неможливо візуально передбачити хід логічного висновку - єдиний предикат-факт, захований десь в кінці тексту програми, може спрямувати роботу в абсолютно непередбачуване русло . В деякому вони праві: труднощі супроводу Prolog-програм і трудність мислення на Prolog для рядових програмістів виявилися непереборними перешкодами для його широкого розповсюдження. Та й, звичайно, у часи розробки Prolog чекали від нього більшого, але потім виявилося, що сам по собі мова програмування допомогти у вирішенні серйозних завдань, наприклад, пов'язаних з прийняттям комп'ютером рішень (machine reasoning), не може.

Інсталяція

[ред.]

Завантажити SWI-Prolog.

Користувачі систем подібних до Debian можуть зробити ще простіше:

sudo apt-get install swi-prolog

Окрім самого компілятора, нам потрібен також звичайний текстовий редактор. Якщо ви виберете Vim, то допишіть в файл ~/.vimrc наступний текст:

autocmd BufRead *.pro nmap <F6> :!prolog -s %<CR>
autocmd BufRead *.pro set syntax=prolog

Це дозволить нам переходити від редагування файлу, одразу до його виконання та взаємодії з ним, а також увімкне правильне підсвічування синтаксису.

Програми на мові пролог краще зберігати в файлах з розширенням .pro, щоб не плутатись їх мовою Perl, хоча якщо ви на ній не програмуєте, то можете використати і .pl.

Інтерфейс користувача

[ред.]

SWI-Prolog запускається командою

swipl

або

prolog

Спочатку, він очікує лише запитів, кожен з яких закінчується крапкою. Спроба написати програму спричинить помилку:

 ?- human(socrates).
ERROR: Undefined procedure: human/1

Тут ?- - привітання системи. Означає що вона очікує запиту.

Програми зберігаються в файлах, і потім передаються інтерпретатору Пролога, за допомогою запиту

?-consult(file). 

який можна написати скорочено:

?-[file].

Щоб ввести програму прямо з клавіатури, потрібно написати команду

?-consult(user).

чи

?-[user].

Тоді все аж до наступного натиснення Ctrl+D дописується в базу даних.

Окрім цього, ви можете запускати пролог одразу з підключеним файлом, написавши:

prolog -s file

, чи якщо в вас налаштований Vim (про що вже було написано вище) - робити це прямо з Vim (кнопкою F6).

Елементи мови

[ред.]

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

Предикат має вигляд

pred(arg1, arg2, ...  argN).

де, pred - його назва, arg1, arg2, ... argN - аргументи, а в кінці обов'язково ставиться крапка. Також можна описати предикат що не має аргументів (нуль-арний), наприклад:

truth.

Варто також зауважити, що алфавіт в версії SWI-Prolog підтримує надмножину набору 16-розрядних символів Unicode[1], тому в програмах можна використовувати кирилицю:

факультет(кібернетики).

Атоми - це певні константи, імена яких починаються з маленької літери, наприклад

hello
multiWordAtom
x32

Для розділювання слів в атомі можна використати символ підкреслювання (але не мінус і не пропуск):

правильна_назва_атома
неправильна назва
ще-одна-неправильна
1_неправильна_бо_починається_не_з_літери

Крім того, атоми можна брати в одинарні лапки, тоді їх можна називати як завгодно:

'Іван Іванов'
'SWI-Prolog'

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

Variable
_1

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

% однорядковий коментар
/*
багаторядковий
коментар
*/

Початок

[ред.]

Створімо файл, наприклад hello.pro, і запишімо в нього, наприклад, такі рядки:

greek(socrates).
greek(plato).
greek(aristotle).

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

?- greek(socrates).
true.

Ще одне питання:

?- greek(diogenes).
false.

бачимо що Пролог не має такого поняття як "не знаю", і завжди дає конкретну відповідь.

Можна запитати:

?- greek(Who).
Who = socrates . 

Who, як і інший довільний ідентифікатор позначає змінну. Варто зауважити, що якщо змінна може мати кілька варіантів, виводиться перший, а далі інерпретатор очікує нашої реації. Якщо ми натиснемо ;, то буде виведено наступний варіант якщо такий є, якщо натиснемо ↵ Enter, то перебір завершиться. Можна отримати всіх греків:

?- greek(X).
X = socrates ;
X = plato ;
X = aristotle.

Щоб завершити інтерактивну сесію, введіть

halt.

І не забувайте ставити крапки наприкінці тверджень. Або натисніть Ctrl+D.

Предикати та запити

[ред.]

Факти в Пролозі задаються за допомогою істинних предикатів. Предикати можуть мати кілька змінних. Наприклад так можна записати факт того, що вчителем Арістотеля був Платон:

mentor(aristotle,plato)

І аналогічно можна записати хто був вчителем Платона:

mentor(plato,socrates).

Тепер, можна запитати хто був вчителем Платона:

?- mentor(plato,X).
X = socrates.

Чи взагалі дати всі можливі пари вчитель - учень:

?- mentor(X,Y).
X = plato,
Y = socrates ;
X = aristotle,
Y = plato.

Можна створити складніший запит:

?- mentor(X,Y),mentor(Y,Z).
X = aristotle,
Y = plato,
Z = socrates.

Тут кома означає кон'юнкцію (логічне "i"), тобто знайти всіх таких X,Y,Z, що Y вчив X, а Z вчив Y.

Анонімна змінна

[ред.]

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

?- mentor(X,_).
X = plato ;
X = aristotle.

Анонімну змінну можна використати також і в описі даних. Вона означатиме "всі" значення. Наприклад:

human(_).

що для довільного аргументу, навіть якщо такий не згадували в базі значення предикату буде true:

?- human(dog).
true.

Правила

[ред.]

Правило в Пролозі виглядає так:

a:- b, c, d.

І означає те, що a буде true, лише коли b, c та d будуть true. Ми можемо створити таку базу даних:

a :- b, c, d.
b.
c.
d :- e.
e.

І коли ми запитаємо a., пролог вияснить, що b і c true, бо так записано, і d true, лише коли e. Але e - теж факт, тому відповідь буде true.

Проте правила цікавіші, коли вони містять предикати зі змінними. Давайте доповнимо наших персонажів учнем Арістотеля - Александром:

greek(socrates).
greek(plato).
greek(aristotle).
macedon(alexander).

mentor(plato,socrates).
mentor(aristotle,plato).
mentor(alexander,aristotle).

Тепер можна написати правило, за яким Греки та Македонці - люди:

human(X):- greek(X);macedon(X).

Крапка з комою означає диз'юнкцію (логічне "або").

?- human(X).
X = socrates ;
X = plato ;
X = aristotle ;
X = alexander.

Можна також придумати правило за яким студентом X є Y, якщо вчителем Y є X.

student(X,Y):- mentor(Y,X).

Рекурсивні правила

[ред.]

Порівняння, присвоєння, співставлення

[ред.]

is - оператор, який обчислює вираз що знаходиться справа від нього, і намагається співставити те що зліва з тим що справа.

?- 4 is 2+2.
true.
?- X is 2+2.
X = 4.

Вирази зліва не зачіпаються.

?- 2+2 is 4.
false.
?- 2+2 = 4.
false.

?- 2+2 == 4.
false.

?- 4 == 4.
true.

?- 4 == 2+2.
false.

?- 2+2 =:= 2+2.
true.

?- X = 2+2.
X = 2+2.

?- X =:= 2+2.
ERROR: =:=/2: Arguments are not sufficiently instantiated

Повнота за Тюрингом

[ред.]

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

 turing(Tape0, Tape) :-
 perform(q0, [], Ls, Tape0, Rs),
 reverse(Ls, Ls1),
 append(Ls1, Rs, Tape).

 perform(qf, Ls, Ls, Rs, Rs) :- !.
 perform(Q0, Ls0, Ls, Rs0, Rs) :-
 symbol(Rs0, Sym, RsRest),
 once(rule(Q0, Sym, Q1, NewSym, Action)),
 action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1),
 perform(Q1, Ls1, Ls, Rs1, Rs).

 symbol([], b, []).
 symbol([Sym|Rs], Sym, Rs).

 action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs).
 action(stay, Ls, Ls, Rs, Rs).
 action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).

 left([], [], Rs0, [b|Rs0]).
 left([L|Ls], Ls, Rs, [L|Rs]).

Простий приклад машини Тюринга визначається фактами:

 rule(q0, 1, q0, 1, right).
 rule(q0, b, qf, 1, stay).

Ця машина виконує збільшення на одиницю числа в унарному кодуванні: вона проходить будь-яке число комірок «1» та додає додаткову «1» у кінці. Приклад запиту та результату:

 ?- turing([1,1,1], Ts).
 Ts = [1, 1, 1, 1] ;

Це показує, як будь-яке обчислення може бути представлено декларативно як послідовність переходів станів, реалізовану в Пролозі як відношення між послідовними станами, що нас цікавлять.

Посилання

[ред.]
  1. Adventure in Prolog
  1. http://www.swi-prolog.org/man/widechars.html