Пролог

Вітаємо вас в вікіпідручнику мови пролог.

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

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

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

Розробка мови 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]. Тоді все аж до наступного натиснення дописується в базу даних.

Окрім цього, ви можете запускати пролог одразу з підключеним файлом, написавши: prolog -s file , чи якщо в вас налаштований Vim (про що вже було написано вище) - робити це прямо з Vim (кнопкою F6).

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

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

Варто також зауважити, що алфавіт в версії SWI-Prolog підтримує надмножину набору 16-розрядних символів Unicodehttp://www.swi-prolog.org/man/widechars.html, тому в програмах можна використовувати кирилицю: факультет(кібернетики).

Атоми - це певні константи, імена яких починаються з маленької літери, наприклад 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, як і інший довільний ідентифікатор позначає змінну. Варто зауважити, що якщо змінна може мати кілька варіантів, виводиться перший, а далі інерпретатор очікує нашої реації. Якщо ми натиснемо , то буде виведено наступний варіант якщо такий є, якщо натиснемо , то перебір завершиться. Можна отримати всіх греків:

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

Щоб завершити інтерактивну сесію, введіть halt. І не забувайте ставити крапки наприкінці тверджень. Або натисніть .

Предикати та запити Факти в Пролозі задаються за допомогою істинних предикатів. Предикати можуть мати кілька змінних. Наприклад так можна записати факт того, що вчителем Арістотеля був Платон: 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).