Пролог
Вітаємо вас в вікіпідручнику мови пролог, дураки!
Вступ
[ред.]Пролог — мова логічного програмування. Пролог заснований на теорії предикатів першого порядку. Назва мови програмування розшифровується як (Програмування в логіці). Ідея використання можливостей наведення теорії предикатів першого порядку — одна з головних переваг мови Пролог для комп'ютерних наук взагалі та штучного інтелекту.
Основними поняттями у мові Пролог є факти, правила логічного висновку та запити, що дозволяють описувати бази знань, процедури логічного виводу та прийняття рішень.
Історія створення і розвитку мови
[ред.]Розробка мови 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), не може.
Інсталяція
[ред.]Користувачі систем подібних до 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] ;
Це показує, як будь-яке обчислення може бути представлено декларативно як послідовність переходів станів, реалізовану в Пролозі як відношення між послідовними станами, що нас цікавлять.