Проло́г (, ) — мова логічного програмування загального призначення, пов'язана зі штучним інтелектом та математичною лінгвістикою.
Пролог має корені в логіці першого порядку, математичній логіці, та, на відміну від багатьох інших мов програмування, є декларативною: логіка програми виражається в термінах відношень, представлених як факти та правила. Обчислення ініціюється запуском запиту над цими відношеннями.
Цю мову програмування спочатку було задумано групою навколо в Марселі на початку 1970-х, а першу систему Пролог було розроблено в 1972-му Аланом Кольмерое та .
Пролог була однією з перших логічних мов програмування,Див. Логічне програмування#Історія. й залишається найпопулярнішою серед таких мов і на сьогодні, маючи декілька безкоштовних та комерційних реалізацій. Її застосовували як для доведення теорем, експертних систем, так і для її початкової області призначення, обробки природної мови. Див. також IBM Watson. Сучасні середовища Прологу підтримують як створення графічних інтерфейсів користувача, так і адміністративні або мережеві застосування.
Пролог добре підходить для розв'язання специфічних задач, що виграю́ть від логічних запитів на базі правил, таких як пошук базами даних, системи голосового керування та заповнення шаблонів.
Синтаксис та семантика
Програмна логіка у Пролозі виражається в термінах відношень, а обчислення ініціюється запуском запиту над цими відношеннями. Відношення та запити створюються з використанням єдиного типу даних Прологу, терму. Відношення виражаються твердженнями. Отримавши запит, рушій Прологу намагається знайти спростування резолюції заперечення запиту. Якщо заперечення запиту може бути спростовано, тобто, знайдено конкретизацію всіх вільних змінних, що робить об'єднання атомарних формул та множини-синґлетону, що складається із заперечення запиту, хибним, то з цього випливає, що початковий запит, із застосуванням знайденої конкретизації, є логічним висновком програми. Це робить Пролог (та інші логічні мови програмування) надзвичайно зручною для застосування в базах даних, символьній математиці та граматичному аналізі мов. Оскільки Пролог дозволяє нечисті предикати, перевірка істинності певних спеціальних предикатів може мати деякий навмисний побічний ефект, як-то виведення значення на екран. Через це програмістові дозволено певною мірою використовувати звичайне імперативне програмування, коли логічна парадигма є незручною. Пролог має як чисту логічну підмножину, що називається «чиста Пролог», так і ряд позалогічних властивостей.
Типи даних
Єдиним типом даних Прологу є терм. Терми можуть бути атомами, числами, змінними або складеними термами.
Атом — це загальна назва без притаманного значення. Прикладами атомів є x, синій, 'Пиріжок' та 'якийсь атом'. Числа можуть бути з рухомою комою, або цілими. Змінні позначаються стрічками, що складаються з літер, цифр та символів підкреслення, і починаються з великої літери або символу підкреслення. Змінні дуже подібні до змінних в логіці тим, що вони є позначками-заповнювачами для довільних термів. Складений терм складається з атому, що зветься функтор, та певної кількості аргументів, що в свою чергу теж є термами. Складені терми зазвичай записуються у вигляді функтора, за яким у дужках слідує перелік термів-аргументів через кому. Кількість аргументів називається арністю терму. Атом може розглядатися як складений терм нульової арності. рік_машини('Таврія', 1988) та 'Друзі_Особи'(грай,[око,тур]) є прикладами складених термів.
Особливі випадки складених термів:
Список є впорядкованою колекцією термів. Він позначається квадратними дужками з термами, розділеними комами, або, у випадку порожнього списку, []. Наприклад, [1,2,3], або [червоний,зелений,синій]. Стрічки: послідовність символів у лапках, еквівалентна спискові (числових) кодів символів, зазвичай у місцевому кодуванні, або в Юнікоді, якщо система підтримує Юнікод. Наприклад, "бути чи не бути".
Правила та факти
Прологові програми описують відношення, визначені твердженнями. Чиста Пролог обмежена диз'юнктами Горна. Є два типи тверджень: факти та правила. Правило має вигляд
Голова :- Тіло.
і читається як «голова істинна, якщо тіло істинне». Тіло правила складається з викликів предикатів, що називаються цілями правила. Вбудований предикат ,/2 (що значить двоарний оператор з ім'ям ,) позначає кон'юнкцію цілей, а ;/2 — диз'юнкцію. Кон'юнкції та диз'юнкції можуть бути присутні лише в тілі, але не в голові правила.
Твердження з порожніми тілами називаються фактами. Наприклад:
кіт(базиліо).
що рівноцінне правилу:
кіт(базиліо) :- true.
Вбудований предикат true/0 є завжди істинним.
Маючи наведений вище факт, можна спитати:
чи є базиліо котом?
?- кіт(базиліо). Yes
що є котами?
?- кіт(X). X = базиліо
Твердження з тілами називаються правилами. Наприклад:
тварина(X):- кіт(X).
Якщо ми додамо це правило та спитаємо, що є тваринами?
?- тварина(X). X = базиліо
Оскільки природа багатьох вбудованих предикатів є відносною, їх зазвичай можна використовувати в кількох напрямках. Наприклад, length/2 може використовуватися як для визначення довжини списку (length(List, L), коли задано список List), так і для створення кістяка списку заданої довжини (length(X, 5)), а також і для створення кістяків списків та їх довжин одночасно (length(X, L)). Так само, append/3 може використовуватися як для з'єднання двох списків (append(ListA, ListB, X) коли задано списки ListA та ListB), так і для розділення заданого списку на частини (append(X, Y, List), коли задано список List). Тому відносно невеликий набір бібліотечних предикатів є достатнім для великої кількості прологових програм.
Як мова загального призначення, Пролог також пропонує різноманітні вбудовані предикати для виконання всякої поточної діяльності, як-то введення/виведення, використання графіки, та іншої взаємодії з операційною системою. Ці предикати не мають значення відношень, і корисні лише для побічних ефектів, що вони спричиняють у системі. Наприклад, предикат write/1 відображає терм на екрані.
Виконання
Виконання прологової програми починається задаванням користувачем єдиної цілі, що зветься запитом. З точки зору логіки, рушій Прологу намагається знайти спростування резолюції заперечення цього запиту. Метод резолюції, що використовується у Пролозі, називається ВЛВ-резолюцією. Якщо заперечення запиту може бути спростовано, з цього випливає, що запит, з відповідними зв'язуваннями змінних, є логічним висновком програми. У такому разі всі створені зв'язування змінних повідомляються користувачеві, і про запит повідомляється, що він досяг успіху. З практичної точки зору, стратегію виконання Прологу можна уявити як узагальнення викликів функцій в інших мовах, з тією різницею, що заданому запитові можуть відповідати голови кількох тверджень. В такому випадку система створює точку вибору, об'єднує ціль з головою твердження першої альтернативи, і продовжує цілями цієї першої альтернативи. Якщо в напрямку виконання програми будь-яка ціль зазнає невдачі, всі зв'язування змінних, що було зроблено від останньої на той момент точки вибору, скасовуються, і виконання продовжується з наступною альтернативою цієї точки вибору. Ця стратегія виконання називається хронологічним пошуком з вертанням. Наприклад:
мати_дитини(ірина, святослав).
батько_дитини(ярослав, святослав). батько_дитини(ярослав, анна). батько_дитини(володимир, ярослав).
брат_або_сестра(X, Y) :- батько_або_мати_дитини(Z, X), батько_або_мати_дитини(Z, Y).
батько_або_мати_дитини(X, Y) :- батько_дитини(X, Y). батько_або_мати_дитини(X, Y) :- мати_дитини(X, Y).
Виходячи з цього, наступний запит оцінюється як істинний:
?- брат_або_сестра(святослав, анна). Yes
Це отримується таким чином: Спочатку єдиною відповідною головою твердження до запиту брат_або_сестра(святослав, анна) є перша, тому надавання запиту є рівноцінним надаванню тіла того твердження з відповідними зв'язуваннями змінних, тобто, кон'юнкція (батько_або_мати_дитини(Z,святослав), батько_або_мати_дитини(Z,анна)). Наступною ціллю для доведення є крайня зліва з цієї кон'юнкції, тобто, батько_або_мати_дитини(Z,святослав). Цій цілі відповідають голови двох правил. Система створює точку вибору, і пробує перший вибір, чиїм тілом є батько_дитини(Z, святослав). Цю ціль може бути доведено з використанням факту батько_дитини(ярослав, святослав), тому створюється зв'язування Z = ярослав, і наступною ціллю для доведення стає друга частина наведеної вище кон'юнкції: батько_або_мати_дитини(ярослав, анна). І знову, це може бути доведено відповідним фактом. Оскільки всі цілі доведено, запит досягає успіху. Оскільки запит не містить жодних змінних, користувачеві не повідомляються жодні зв'язування. Запит зі змінними, як-то:
?- батько_дитини(Батько, Дитина).
перелічує всі дійсні відповіді пошуку з вертанням.
Зверніть увагу, що з наведеним вище кодом запит ?- брат_або_сестра(святослав, святослав). також досягає успіху. Якщо потрібно, можна додати додаткові цілі для опису відповідних обмежень.
Цикли та рекурсія
Ітеративні алгоритми може бути реалізовано засобами рекурсивних предикатів.
Заперечення
Вбудований предикат Прологу \+/1 забезпечує заперечення як відмову, що уможливлює немонотонну аргументацію. Ціль \+ нелегальне(X) у правилі
легальне(X) :- \+ нелегальне(X).
обчислюється таким чином. Пролог намагається довести нелегальне(X). Якщо доведення цієї цілі знайдено, то початкова ціль (тобто, \+ нелегальне(X)) зазнає невдачі. Якщо доведення не може бути знайдено, то початкова ціль досягає успіху. Отже, префіксний оператор \+/1 називається оператором «недовідне», оскільки запит ?- \+ Ціль. досягає успіху, якщо Ціль не є довідною. Цей вид заперечення є правильним, якщо його аргумент є замкненим (тобто, не містить змінних). Правильність втрачається, якщо аргумент містить змінні, і процедура доведення є повною. Зокрема, запит ?- легальне(X). тепер вже не може бути використано для перелічення усіх речей, що є легальними.
Програмування мовою Пролог
У Пролозі завантаження коду називається взяттям до уваги. Пролог може використовуватися інтерактивно шляхом введення запитів до підказки Прологу, ?-. Якщо розв'язку не існує, то Пролог пише no. Якщо розв'язок існує, то тоді друкується він. Якщо існує декілька розв'язків запиту, то їх може бути запитано введенням крапки з комою, ;. Існують керівні принципи з належної практики програмування для покращення ефективності, читабельності та підтримуваності коду.
Далі слідують деякі приклади програм, написаних мовою Пролог.
"Hello, world!"
Приклад запиту: ?- write('Привіт, світе!'), nl. Привіт, світе! true.
?-
Оптимізація компілятором Будь-яке обчислення може бути виражено декларативно як послідовність переходу станів. Як приклад, оптимізувальний компілятор з трьома проходами оптимізації може бути реалізовано як відношення між початковою програмою та її оптимізованою формою:
програма_оптимізована(Прог0, Прог) :- оптимізація_прохід_1(Прог0, Прог1), оптимізація_прохід_2(Прог1, Прог2), оптимізація_прохід_3(Прог2, Прог).
або рівнозначно з використанням запису граматики визначених тверджень:
програма_оптимізована --> оптимізація_прохід_1, оптимізація_прохід_2, оптимізація_прохід_3.
Швидке сортування
Алгоритм швидкого сортування, що ставить у відповідність спискові його відсортовану версію: розділення([], _, [], []). розділення([X|Xs], Опорне, Малі, Великі) :- ( X @< Опорне -> Малі = [X|Решта], розділення(Xs, Опорне, Решта, Великі) ; Великі = [X|Решта], розділення(Xs, Опорне, Малі, Решта) ).
швидке_сортування([]) --> []. швидке_сортування([X|Xs]) --> { розділення(Xs, X, Менші, Більші) }, швидке_сортування(Менші), [X], швидке_сортування(Більші).
Шаблони проектування