Лекція присвячена вирішенню завдань за допомогою графа простору станів. Простір станів описується як безліч станів – вершин графа, безлічі переходів стану до стану – дуг графа, безлічі початкових станів і безлічі кінцевих станів. Розв'язання задачі представляється у вигляді шляху на графі простору станів, що сполучає початковий стан із кінцевим. Якщо простір станів завдання невеликий, будуть знаходитися всі оптимальні рішення за допомогою пошуку в глибину. У завданнях з великим простором станів обчислюватиметься лише одне оптимальне рішення шляхом пошуку шириною. До завдань застосовуються універсальні вирішувачі. Стани у різних завданнях можуть належати різним доменам. Для запам'ятовування найкращих серед знайдених рішень використовується "змінна змінна" varM. Компілятор знаходить потрібні типи. Версія Visual Prolog 7.5 ще не опублікована. Її публікація планується у 2014 році, але точна дата поки що не відома. Наразі всім доступна версія Visual Prolog 7.4.

І розглянути рішення найпростіших завдань на Пролозі.

Перш ніж починати, хотілося б коротко відповісти на злободенні питання від хабрачитачів:
- Де реально використовується пролог?
- Такі проекти існують, деякі наводилися у коментарях до 1-ї статті. Важливо, що більшість програмістів пишуть на Пролозі не від безвиході, а від того, що їм подобається Пролог. Зрештою, Пролог не може використовуватися для будь-якого завдання, такого створення UI або маніпулювання з файлами.

Чому таких проектів мало?
- Тому що програмістів, які володіють Пролог, вкрай мало, не тільки тому, що люди не вивчали його, а тому що недовивчали для написання повних програм. Головна ж причина, що люди недостатньо чітко розуміють, у яких ситуаціях найкраще його використовувати. Часто можна бачити, що затяті прихильники Прологу, пишуть на ньому все, включаючи обробників клавіатури та миші, через що код виходить ще гірше, ніж на С.

Чому немає спільноти Прологу?
– Воно є. Така специфіка мови, що він дуже полюбився в академічному середовищі (більшість Prolog систем пишуться в різних університетах і, навпаки, практично будь-який університет пише свій Пролог), через це можна сказати страждає і застосовність мови. Варто відзначити, що спільнота невелика, але дуже лояльна: практично всі відомі мови знайшли своє відображення в сучасних мовах (Lisp, ML -> F#, Scala; Smalltalk -> Java, Scala (агенти), скриптові -> Ruby), на відміну від Пролог.

Думаю на цьому вистачить філософських міркувань і можна розпочати реальні приклади:)

Наприкінці зазвичай чекає завдання на приз.

Приклад №1 - пошук досконалих чисел

Для цього прикладу знадобиться предикат is/2. X is 3 + 1 * 2- обчислює вираз праворуч і заносить у змінну зліва, це привласнення (!), а твердження що X = 7. Простіше кажучи фраза X = 7, X = 3 - немає рішення оскільки X може бути одночасно 7 і 3.
Також нам знадобиться вирішення завдання з попереднього топіка. Завдання було написати предикат, який генерував би всі натуральні числа поспіль, ось рішення:
ints(0). ints(X) :- ints(Y), X is Y + 1.
Насправді це декларативна версія стандартного предикату integer/1, який перевіряє, що аргумент є цілим числом. Проблема стандартного предикату, що він працює правильно для запиту: - integer (1) і не працює для запиту integer (X).

Завдання: написати програму, яка б знаходила всі досконалі числа
Рішення очевидно, пробігаємо за всіма цілими числами і перевіряємо чи вони є досконалими, ця стратегія дуже добре застосовна до імперативним мовам, ми й самі не помічаємо, як ми шукаємо алгоритм пошуку рішення, а чи не аналізуємо завдання. У Пролозі ми повинні не намагатися описати пошук розв'язання задачі, а намагатися описати постановку задачі, щоб зробити це керуйтесь правилом:

Не намагайтеся описати інструкції пошуку рішення, припустіть, що ви вже знайшли рішення, а ваше завдання лише перевірити, що рішення знайдено.

Як не дивно, але ця стратегія чудово працює.
%% Декларативне визначення натуральних чисел ints(0). ints(X) :- ints(Y), X is Y + 1. %% Вчинене число - це 1) натуральне число 2) сума дільників дорівнює числу perfect_number(X) :- ints(X), Y is X - 1, calculatesum_divisors_till(Sum, X, Y), Sum = X. %% Перевірка суми дільників 1-й аргумент Сума, 2-й – число для якого шукаємо дільники, %% 3-е – число до якого шукаємо дільники calculatesum_divisors_till(0, _NumberToDivide 0). calculatesum_divisors_till(Sum, NumberToDivide, Till) :- Till > 0, Rem is NumberToDivide mod Till, Rem = 0, Ts is Till - 1, calculatesum_divisors_till(SumPrev, NumberToDivide, Ts), Sum is calculatesum_divisors_till(Sum, NumberToDivide, Till) :- Till > 0, Rem is NumberToDivide mod Till, Rem > 0, Ts is Till - 1, calculatesum_divisors_till(Sum, NumberToDivide, Ts).

Вставляємо вихідний текст у файл, запускаємо інтерпретатор та компілюємо його (через запит:-compile("шлях_к_файлу/perfect_numbers.pl")). :- perfect_number(X).та інтерпретатор видає відповідь, при натисканні ";" видає наступний. Зверніть увагу запит може бути :- perfect_number(X), X > 6. Тоді всі відповіді будуть більшими за 6. Звичайно програма працює не оптимально, сама перевірка може бути спрощена з використанням простих дільників, спробуйте.

Приклад №2 – генерація перестановок.

Для постановки та вирішення цього завдання нам знадобиться поняття списків. Списки не є базовим поняттяммови, між списками можна провести пряму аналогію зі зв'язковими списками в C. Повернемося до визначення терму як до рекурсивної структури даних.
%% Визначимо порожній список як об'єкт nil list(nil). %% Визначимо список одного елемента 1 list(t(1, nil)). %% Визначимо список елементів 1, 2, 3 list(t(1, t(2, t(3, nil)))). %% Опишемо наприклад процедуру пошуку в списку %% 1. результат знаходиться в голові списку (1-й елемент) %% _ - означає незначну нам змінну member(X, t(Y, _)) :- X = Y. %% 2. результат не перший елемент, але міститься у хвості списку після першого елемента member(X, t(_, Tail)) :- member(X, Tail).

Як багато хто сказав звичайна рекурсія і щоб списки не виглядали якось особливо в Пролозі існує синтаксичний цукор для них: nil можна записати , t(1, nil) - , t(1, t(2, nil)) - , t( 1, Sublist) - , t(1, t(2, Sublist)) - . Рекомендується користуватися синтаксичним цукром для списків, тому що внутрішня назва термів може відрізнятися (найчастіше терм називається ".").
%% 1. результат перебуває у голові списку (1-й елемент) member(X, ). %% 2. результат не перший елемент, але міститься у хвості списку після першого елемента member(X, [_| Tail]) :- member(X, Tail).
Повернемося до вихідної задачі створення перестановок. Всі чудово пам'ятають, що кількість перестановок n!, але дай це завдання більшості програмістів і всі почнуть судомно згадувати і говорити, що писали це в школі і забули як робиться перебір. У середньому алгоритм з'являється після старань і мук через 20 хвилин. При знанні Прологу цей алгоритм пишеться за 2 хвилини або не пишеться взагалі:)

Як вирішити на Пролозі? Скористаємося правилом не пошуку рішення, а перевірки, що рішення знайдено. Предикат perm(Source, Permutation)- де Source вихідний список, Permutation – перестановка.

%% Якщо вихідний список порожній, то існує одна перестановка порожній список perm(, ). %% 1-й елемент перестановки повинен утримуватися у вихідному списку, %% при чому його треба відразу виключити з оригінального списку, %% інші елементи повинні бути перестановкою перестановкою %% оригінального списку, що залишився perm(Source, ) :- member_list_exclude(Element, Source , SourceExcluded), perm(SourceExcluded, Tail). %% Перевірка того, що елемент міститься в списку, а 2-й список є списком без елемента %% Назва предикату member_list_exclude відповідає порядку аргументів %% 1-й – елемент, 2-й – список, 3-й – список без елементів member_list_exclude (X, , L). member_list_exclude(X, , ) :- member_list_exclude(X, L, Ls).
Запит :-perm(, X)генерує всі перестановки. Цікаво, що запити симетричні :-perm(X, )щодо аргументів, щоправда даний запитзависає і щоб він працював необхідно поміняти member_list_exclude та perm місцями в perm.

Приклад №3 – генерація поєднань.

Генерація сполучень за простотою реалізації схожа на генерацію перестановок. Нам знадобиться предикат member/2 – приналежність елемента до списку. Припустимо, у нас є 2 списки: 1-й вихідний список, 2-й - передбачуване поєднання, необхідно перевірити правильність поєднання. Елементи поєднання розміщуються порядку вихідного списку.

Member(X, ). member(X, [_|L]) :- member(X, L). comb(,). %% Варіант 1: 1-й елемент поєднання міститься у вихідному списку comb(, ) :- comb(List, Tail). %% Варіант 2: поєднання є правильним поєднанням хвоста списку, %% тобто 1 елемент вихідного списку не міститься в поєднанні comb([_|List], Tail) :- comb(List, Tail).

Приклад №4 – сортування.

Даний приклад розглянемо досить докладно та спробуємо провести оптимізацію первинного рішення. Процес написання на Пролозі виглядає наступним чином: 1) первинне опис завдання та отримання перебірного рішення 2) логічна оптимізація перестановкою предикатів праворуч 3) логічна оптимізація введення спрощених перевірок або видалення зайвих умов 4) введення евристик та оптимізація окремих випадків шляхом.

Варіант 1. Сортування наївне: перший елемент відсортованого масиву має бути мінімальним, інші елементи мають бути відсортовані. Перший масив вихідний, другий відсортований масив вихідний.

Sort(, ). sort(List, ) :- min_list_exclude(Min, List, Exclude), sort(Exclude, SortRest). %% Рекурсивно виключаємо мінімальне число, якщо у списку одне число виключаємо min_list_exclude(M, [M], ). min_list_exclude(Min, , ExcludeRes) :- min_list_exclude(Ms, L, Exclude), find_result(result(M, L), result(Ms, ), result(Min, ExcludeRes)). %% Додатковий предикат для визначення пари з мінімальним ключем find_result(result(M, L), result(Ms, _), result(M, L)):- M< Ms. find_result(result(M, _), result(Ms, Exclude), result(Ms, Exclude)):- Ms =< M.
Можна помітити, що складність даного алгоритму є квадратичною і основною проблемою в тому, що ми щоразу шукаємо мінімальний елемент, не зберігаючи при цьому жодної корисної інформації.
Зазначимо також, що ми намагаємося визначити, що таке перший елемент відсортованого масиву.

Варіант 2. Швидке сортування.Подивимося на проблему з другого боку та спробуємо визначити місце 1-го елемента списку у відсортованому масиві (застосовуємо рекурсію до вихідного масиву).

Sort_b(,). sort_b(, List) :- split(T, R, Less, Great), sort_b(Less, LessSort), sort_b(Great, GreatSort), append(LessSort, , List). %% Розділяємо масив на 2 масиви більше та менше split(_, ,, ). split(T, ,, Great) :- M< T, split(T,R, Less,Great). split(T, ,Less, ) :- M >= T, split (T, R, Less, Great). %% Склеюємо 2 списки append(, M, M). append(, Right, ) :- append(Left, Right, Res).
Можна помітити, що ми покращили результати сортування, так як швидке сортування свідомо швидше бульбашкового. Для того, щоб ще покращити результати, ми можемо згадати сортування злиттями, яке у будь-якому випадку дає O(n lg n), але на жаль дане сортуваннязастосовна лише до масивів, а чи не до зв'язковим списку, із якими ми працюємо. Єдиний варіант використовувати додаткову структуру даних для зберігання – дерево.

Варіант 3. Сортування за допомогою бінарного дерева.

Для цього виду сортування переведемо вихідний список у бінарне дерево, а потім, скориставшись обходом дерева зліва, отримаємо відсортований масив. Дерево представлятимемо рекурсивним термом tree(Object, LeftSubTree, RightSubTree).
sort_tree(, nil). sort_tree(, Tree) :- sort_tree(L, LTree), plus(X, LTree, Tree). %% Додавання елемента до дерева plus(X, nil, tree(X, nil, nil)). plus(X, tree(O, L, R), tree(O, ResL, R)) :- O >= X, plus(X, L, ResL). plus(X, tree(O, L, R), tree(O, L, ResR)) :- O< X, plus(X, R, ResR). sort_t(X, Y) :- sort_tree(X, Tree), tree_list(Tree, Y). append_list(, L, L). append_list(, R, ) :- append_list(L, R, T). tree_list(nil, ). tree_list(tree(X, L, R), List) :- tree_list(L, ListL), tree_list(R, ListR), append_list(ListL, , List).

Варіант 4. Сортування за допомогою збалансованого бінарного дерева.

Проблема використання бінарного дерева така ж як використання швидкого сортування. Метод не гарантує оптимальної роботи. У випадку бінарного дерева дерево може бути розбалансоване і процедура додавання елемента в нього може бути лінійна, а не логарифмічна. Спеціально для цього виконуються процедури балансування дерева, нижче для ознайомлення буде наведено алгоритм з використанням АВЛ-дерева.

Sort_btree (X, Y) : - sort_tree (X, Tree), tree_list (Tree, Y). tree_list(nil,). tree_list(tree(X, L, R, _), List) :- tree_list(L, ListL), tree_list(R, ListR), append(ListL, , List). sort_tree(, nil). sort_tree(, Tree) :- sort_tree(L, LTree), plus_tree(X, LTree, Tree). construct_tree(A, AL, AR, tree(A, AL, AR, ADepth)) :- diff(AL, AR, _, ADepth). diff(AL, AR, ADiff, ADepth) :- depth_tree(ALs, AL), depth_tree(ARs, AR), ADiff is ALs - ARs, max_int(ALs, ARs, AD), ADepth is AD + 1. max_int(A , B, A) :- A > B. max_int(A, B, B) :- A =< B. append(, L, L). append(, R, ) :- append(L, R, T). depth_tree(0, nil). depth_tree(X, tree(_, _, _, X)). plus_tree(X, nil, tree(X, nil, nil, 1)). plus_tree(X, tree(O, L, R, _), Res) :- O >= X, plus_tree(X, L, ResL), diff(ResL, R, Diff, Dep), balance_tree(tree(O, ResL, R, Dep), Diff, Res). plus_tree(X, tree(O, L, R, _), Res) :- O< X, plus_tree(X, R, ResR), diff(L, ResR, Diff, Dep), balance_tree(tree(O, L, ResR, Dep), Diff, Res). %% No rotations balance_tree(Tree, ADiff, Tree) :- ADiff < 2, ADiff >-2. %% Small right rotation balance_tree(tree(A, tree(B, BL, BR, _), AR, _), ADiff, Result) :- ADiff > 1, diff(BL, BR, BDiff, _), BDiff > = 0, construct_tree(A, BR, AR, ASubTree), construct_tree(B, BL, ASubTree, Result). %% Big right rotation balance_tree(tree(A, tree(B, BL, BR, _), AR, _), ADiff, Result) :- ADiff > 1, diff(BL, BR, BDiff, _), BDiff< 0, BR = tree(C, CL, CR, _), construct_tree(B, BL, CL, BSubTree), construct_tree(A, CR, AR, ASubTree), construct_tree(C, BSubTree, ASubTree, Result). %% Small left rotation balance_tree(tree(A, AL, tree(B, BL, BR, _), _), ADiff, Result) :- ADiff < -1, diff(BL, BR, BDiff, _), BDiff =< 0, construct_tree(A, AL, BL, ASubTree), construct_tree(B, ASubTree, BR, Result). %% Big left rotation balance_tree(tree(A, AL, tree(B, BL, BR, _), _), ADiff, Result) :- ADiff < -1, diff(BL, BR, BDiff, _), BDiff >0, BL = tree(C, CL, CR, _), construct_tree(B, CR, BR, BSubTree), construct_tree(A, AL, CL, ASubTree), construct_tree(C, ASubTree, BSubTree, Result).
Даний приклад не є досить виразним для реалізації на Пролозі, хоч і дає уявлення про програми середнього обсягу. Для тренування можна реалізувати бульбашкове сортування або сортування вставками, залишимо це на розсуд читача.

Приклад №5 - Завдання про переливання.

Як наступне завдання розглянемо класичну задачу про стани, ця задача набагато краще відображає переваги використання Прологу. Загальна постановка завдання: дані деякі ємності з водою, необхідно шляхом переливань отримати певну кількість води в деякій ємності. Для прикладу візьмемо 3 глечика ємністю 12 літрів, 8 літрів, 5 літрів, наповнимо 1-й повністю, тобто 12 літрами і поставимо завдання отримати 6 літрів. Для початку спробуйте вирішити це шкільне завдання за допомогою ручки та аркуша паперу :)

Перш ніж генерувати різні алгоритми і намагатися застосувати їх до завдання, давайте спочатку перепишемо умови в термінах Прологу. Опишемо ємність як терм sosud(Id, MaximumCapacity, CurrentCapacity), стан системи опишемо як список ємностей Приклад . Тепер опишемо запит:

%% solve_pr_wo(InitialState, Goal, Steps). :- solve_pr_wo(, sosud(X, _, 6), Steps).

Зверніть увагу, що Goal = sosud(_, _, 6), тобто нам не важливо якої ємності посудина головне щоб у ньому було саме 6 літрів.

Тепер коли нам все відомо опишемо спосіб перевіркирішення, вважаючи, що кроки задані в змінній Steps.

%% Для отримання стану не потрібно жодного кроку, %% означає один із судин знаходиться у списку solve_pr_wo(State, Goal, ) :- member(Goal, State). %% Перший крок це перелити з Sosud в Sosud2 і отримати стан %% першої судини ResSosud, а другої ResSosud2. %% Конкретний приклад кроку: %% mv(sosud(1, 12, 12) -> sosud(2, 8, 0), sosud(1, 12, 4) -> sosud(2, 8, 8)). solve_pr_wo(State, Goal, ) :- %% В першу чергу перевірка домену, що судини дійсно %% містяться в поточному стані і вони не рівні один одному member(Sosud, State), member(Sosud2, State), not(Sosud = Sosud2), %% Здійснення самого переливання, тут %% беруть участь усі 4 змінні кроки mv(Sosud, Sosud2, ResSosud, ResSosud2), %% Заміна стану судин у списку станів по черзі replace(Sosud, State, ResSosud, State2), replace (Sosud2, State2, ResSosud2, StateX), %% Подальші кроки повинні виконуватися за рекурсією solve_pr_wo(StateX, Goal, Steps). %% Насправді звичайна заміна елемента у списку %% replace(ElementToReplace, InList, ElementToReplaceWith, OutList). replace(S, , X, ). replace(S, , X, ) :- replace(S, L, X, Ls). %% Процедура переливання - 2 варіанти %% вихідна судина буде вичерпана або цільова наповнена %% Спустошення першої судини у другій mv(sosud(Id1, Max1, Current), sosud(Id2, Max2, Current2), sosud(Id1, Max1, 0 ), sosud(Id2, Max2, Current3)) :- Current >< Max2. %% Переливание из первого сосуда до краев второго mv(sosud(Id1, Max1, Current), sosud(Id2, Max2, Current2), sosud(Id1, Max1, Current3), sosud(Id2, Max2, Max2)) :- Current >0, Current3 є Current2 + Current - Max2, Current3 >= 0.

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

Що ж, опис програми написано – можна запустити. Не варто дивуватися програма не запрацює, воно просто зависне:) Це не так погано, як може здатися, тому що якби програма не зависла, то вона видала б правильну відповідь. Слід розібратися чому ж вона зависла і тут нам на допомогу прийде розуміння як Пролог розгортає правила, щоб знайти рішення. Насправді, не треба мати голову здатну запам'ятати до 10 точок повернення, щоб зрозуміти, що кожен наступний раз коли solve_pr_wo -> викликає по рекурсії solve_pr_wo, він викликає 2 предиката member/2, які завжди видають одне й те саме 1-й і 2-а судина (предикат not викликає backtracking і не дозволяє member вибрати 1-ю і 1-ю судину). Тобто алгоритм постійно переливає з 1 до 2 і назад.

Для того, щоб вирішити цю безглуздість, на думку відразу приходить заборонити робити одну і ту ж дію 2 рази, тобто мати стани і якщо стан вже зустрічалося, то заборонити його повторне влучення. Виходить, що ми звужуємо безліч допустимих стратегій переливання, крім повторень. Насправді звужуючи безліч стратегій, ми звужуємо безліч допустимих станів системи, тобто рішень, що важко довести.

Повна версія програма з роздруківкою станів та єдиним предикатом для виклику solution:

Write_list(). write_list() :- writeln(X), write_list(L). solution:- solve_pr(, sosud(_, _, 6), , Steps), write_list(Steps). replace(S, , X, ). replace(S, , X, ) :- replace(S, L, X, Ls). %% вважатимемо стратегією переливання не самі кроки, а просто кінцеві стани %% знаючи початковий і кінцевий стан, не важко здогадатися, який крок був виконаний solve_pr(State, Goal, _, ) :- member(Goal, State). solve_pr(State, Goal, History, ) :- member(Sosud, State), member(Sosud2, State), not(Sosud = Sosud2), mv(Sosud, Sosud2, ResSosud, ResSosud2), replace(Sosud, State, ResSosud , State2), replace(Sosud2, State2, ResSosud2, StateX), %%% та сама перевірка кінцевого стану not(member(StateX, )), solve_pr(StateX, Goal, , Steps). %% mv(sosud(_Id, Max, Current), sosud(_Id2, Max2, Current2), ...,...). %% Спустошення першої судини в другій mv(sosud(Id1, Max1, Current), sosud(Id2, Max2, Current2), sosud(Id1, Max1, 0), sosud(Id2, Max2, Current3)) :- Current > 0 , Current3 is Current2 + Current, Current3 =< Max2. %% Переливание из первого сосуда до краев второго mv(sosud(Id1, Max1, Current), sosud(Id2, Max2, Current2), sosud(Id1, Max1, Current3), sosud(Id2, Max2, Max2)) :- Current >0, Current3 є Current2 + Current - Max2, Current3 >= 0.

Все тепер працює! Як вправу можна модифікувати програму, щоб вона знаходила переливання за оптимальну кількість кроків. Можете поекспериментувати на цих завданнях.

Зауваження: затяті прихильники імперативного програмування помітять, що все, що ми зробили це перебір всіх станів із поверненнями (прохід у глибину), причому без використання евристик, і будуть абсолютно праві. Справа в тому, що мислити в Пролозі потрібно якраз не перебором, а описом завдання та описом перевірки рішення, а до імперативності обчислень завжди потрібно повертатися для оптимізації, якщо вона потрібна! Двоїстість природи – не мінус, а плюс. Варто також відзначити, що великі прологові системи дуже добре адаптовані для пошуку станів з поверненнями.

Висновок

Хотілося б зазначити, що розглянуті у цій статті є етюдами для програмування на Пролозі. Так як більшість з них займає близько 10-15 рядків, то програміст на Пролозі може відтворити їх по пам'яті при достатньому частому розв'язанні їх. А повертатися до них обов'язково варто, тому що це нагадує про мистецтво програмування (так само як швидке сортування на C). Більш складні та прикладні завдання для повсякденного використання будуть розглянуті пізніше.

Наприкінці аж 2 завдання на приз:

1. Як відомо у функціональному та логічному всіляко намагаються уникнути програм із side ефектами, обертають їх у монади, вигадують спеціальні концепції. Стандартна проблема - це проблема зовнішнього світу, наприклад, запис даних у файл, неможливо відкотити запис у файл або скасувати відсилання кількох байт по сокету, а отже, бектрекінг буде працювати не зовсім коректно. Порада одна - не використовуйте для цього Пролог. Але є такі предикати, які дуже гарні та специфічні для Прологу, але мають side effect. Приклад assert (asserta, assertz): він додає основу правил (фактів) просте правило (факт). Приклад assert(prime(3)): додає факт, що 3 просте число і запит :-prime(X), тепер буде видавати 3, навіть при порожній вихідній програмі.

   Завдання: написати декларативну версію assert, тобто при поверненні програми з бектрекінг факт не повинен залишатися в пам'яті, а повинен працювати як логічне припущення.

   Приклад роботи: запит c(X) повинен видавати одне число 4 для наступної програми!
   a(X) :- b(Y), X is Y + 1 . c(X) :- my_assert(b(3)), a(X). c(X) :- b(X).

2. У класичній математичній логіці 2 теоріям приділяється набагато більше уваги, ніж решті - це теорія множині теорія предикатів. Між ними існує певний зв'язок, одне виражається через інше і навпаки. Наприклад, предикат - це безліч значень, на яких він істинний, і навпаки, безліч - це предикат приналежності. Традиційна реляційна теорія баз даних оперує множинами, а Пролог оперує – предикатами. Загалом, завдання полягає в тому, щоб висловити абсолютно традиційну для теорії множин операцію. операцію взяття множини всіх підмножин.

   Завдання: дано деякий одномісний предикат a/1 (загалом безліч елементів не обмежена, може бути нескінченно), написати предикат subset_a/1, який буде видавати підмножини, що складаються з елементів множини a.

   Приклад: запит subset_a(X) видає X = , X = , X = , X = (порядок не важливий):
   a(1). a(2). subset_a(X) :- ....?

Спасибі за увагу.

Теги: Додати теги

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

У жовтні 1981 року Японське міністерство міжнародної торгівлі та промисловості оголосило про створення дослідницької організації – Інституту з розробки методів створення комп'ютерів нового покоління (Institute for New Generation Computer Technology Research Center). Метою цього проекту було створення систем обробки інформації, що базуються на знаннях. Передбачалося, що це системи забезпечуватимуть простоту управління з допомогою можливості спілкування з користувачами з допомогою природного мови. Ці системи повинні були самонавчатися, використовувати знання знання для вирішення різноманітних завдань, надавати користувачам експертні консультації, причому від користувача не вимагалося бути фахівцем в інформатиці. Передбачалося, що людина зможе використовувати ЕОМ п'ятого покоління так легко, як будь-які побутові електроприлади типу телевізора, магнітофона і пилососа. Незабаром слідом за японським стартували американський та європейський проекти.

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

Тепер уже зрозуміло, що поставленої мети повною мірою так і не було досягнуто, однак цей проект послужив імпульсом до розвитку нового витка досліджень у галузі штучного інтелекту та викликав вибух інтересу до логічного програмування. Оскільки ефективної реалізації традиційна фон неймановская архітектура не підходила, було створено спеціалізовані комп'ютери логічного програмування PSI і PIM .

Як основна методологія розробки програмних засобівдля проекту ЕОМ п'ятого покоління було обрано логічне програмування, яскравим представником якого є мова Пролог . Здається, що і в даний час Пролог залишається найбільш популярною мовою штучного інтелекту в Японії та Європі (у США, традиційно, більш поширена інша мова штучного інтелекту – мова функціонального програмування Лісп).

Назва мови "Пролог" походить від слів ЛОГІЧНЕ ПРОграмування(PROgrammation en LOGique у французькому варіанті та PROgramming in LOGic - в англійському).

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

У історії виникнення та розвитку мови Пролог можна назвати такі етапи.

У 1965 році в роботі "A machine oriented logic based on the resolution principle", опублікованій у 12 номері журналу "Journal of the ACM", Дж Робінсон представив метод автоматичного пошуку доказу теорем у обчисленні предикатів першого порядку, що отримав назву " принцип резолюції". Цю роботу можна прочитати в перекладі: Робінсон Дж. Машинно-орієнтована логіка, заснована на принцип резолюції// Кібернетичний збірник. - Вип. 7 (1970). Насправді, ідея даного методубула запропонована Ербраном у 1931 році, коли ще не було комп'ютерів (Herbrand, "Une methode de demonstration", These, Paris, 1931). Робінсон модифікував цей метод так, що він став придатним для автоматичного, комп'ютерного використання, і, крім того, розробив ефективний алгоритм уніфікації, що є базисом його методу.

У 1973 році "група штучного інтелекту" на чолі з Аланом Колмерое створила в Марсельському університеті програму, призначену для доказу теорем. Ця програма використовувалася при побудові систем обробки текстів природною мовою. Програма підтвердження теорем отримала назву Prolog (від Programmation en Logique). Вона і стала прообразом Прологу. Ходять легенди, що автором цієї назви була дружина Алана Колмерое. Програма була написана на Фортрані та працювала досить повільно.

Велике значення у розвиток логічного програмування мала робота Роберта Ковальського " Логіка предикатівяк мова програмування(Kowalski R. Predicate Logic as Programming Language. IFIP Congress, 1974), в якій він показав, що для того, щоб досягти ефективності, потрібно обмежитися використанням множини хорнівських диз'юнктів. До речі, відомо, що Ковальський та Колмерое працювали разом протягом одного літа.

У 1976 р. Ковальський разом із його колегою Маартеном ван Емденом запропонував два підходи до прочитання текстів логічних програм: процедурний та декларативний. Про ці підходи йтиметься у третій лекції.

У 1977 році в Единбурзі Уоррен і Перейра створили дуже ефективний компілятор мови Пролог для ЕОМ DEC-10, який був прототипом для багатьох подальших реалізацій Прологу. Що цікаво,

Мова програмування

Prolog (від "PROgramming in LOGic") - декларативна мова програмування загального призначення.

Prolog був створений у 1972 році з метою поєднувати використання логіки з поданням знань. З того часу в нього з'явилася низка діалектів, що розширюють основу мови різними можливостями.

Стандарт мови надано ISO/IEC 13211-1 (1995 рік).

Prolog - одна з найстаріших і все ще одна з найбільш популярних мов логічного програмування, хоча вона значно менш популярна, ніж основні імперативні мови. Він використовується в системах обробки природних мов, дослідженнях штучного інтелекту, експертних системах, онтології та інші предметних областях, котрим природно використання логічної парадигми.

Prolog був створений під впливом більш ранньої мови Planner і запозичив із неї наступні ідеї:

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

Головною парадигмою, реалізованою у мові Prolog, є логічне програмування. Як і для більшості старих мов, більш пізні реалізації, наприклад Visual Prolog , додають в мову пізніші парадигми, наприклад, об'єктно-орієнтоване або кероване подіями програмування, іноді навіть з елементами імперативного стилю.

Prolog використовує один тип даних, терм, який буває кількох типів:

• атом- ім'я без особливого сенсу, що використовується для побудови складових термів;
• числаі рядкитакі ж, як і в інших мовах;
• зміннапозначається ім'ям, що починається з великої літери, і використовується як символ-заповнювач для будь-якого іншого термо;
• складовий термскладається з атома-функтора, за яким слідує кілька аргументів, кожен з яких у свою чергу є атомом.

Програми, написані на чистому Prolog, описують відносини між оброблюваними сутностями з допомогою клауз Хорна. Клауза - це формула вигляду Голова: - Тіло. , яка читається як “щоб довести/вирішити Голову, слід довести/вирішити Тіло”. Тіло клаузи складається з кількох предикатів (цілей клаузи), скомбінованих за допомогою кон'юнкції та диз'юнкції. Клаузи з порожнім тілом називаються фактами та еквівалентні клаузам виду Голова: - true. (True - не атом, як в інших мовах, а вбудований предикат).

Іншою важливою частиною Prolog є предикати. Унарні предикати виражають властивості їх аргументів, тоді як предикати з кількома аргументами висловлюють стосунки з-поміж них. Ряд вбудованих предикатів мови виконують ту ж роль, що й функції інших мов, наприклад, ….

Предикати з кількома аргументами можуть діяти в кількох напрямках залежно від того, які аргументи вже пов'язані, а які — ні. Наприклад, ….

Нарешті, для того, щоб бути мовою загального призначення, Prolog повинен надавати низку сервісних функцій, наприклад процедур введення/виводу. Вони реалізовані як предикати без спеціального логічного сенсу, які завжди оцінюються як істинні та виконують свої сервісні функції як побічний ефект оцінювання.

Метою виконання програми на Prolog є оцінювання одного цільового предикату. Маючи цей предикат і набір правил і фактів, заданих у програмі, Prolog намагається знайти прив'язки (значення) змінних, у яких цільовий предикат набуває значення істинності.

…

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

В усіх інших відносинах Пролог не відрізняється від традиційних мов програмування. Як і у випадку програми написаної будь-якою іншою мовою, Пролог-програма призначена для вирішення окремого завдання.

Пролог (Prolog) - мова логічного програмування, заснований на логіці диз'юнктів Хорна, що є підмножиною логіки предикатів першого порядку. Початок історії мови належить до 70-х років ХХ століття. Будучи декларативною мовою програмування, Пролог сприймає як програму деякий опис завдання, і сам здійснює пошук рішення, користуючись механізмом бектрекінгу та уніфікацією.

Пролог відноситься до так званих декларативних мов, що вимагають від автора вміння скласти формальний опис ситуації. Тому програма на Пролозі не є такою у традиційному розумінні, тому що не містить керуючих конструкцій типу if...then, while...do; немає навіть оператора привласнення. У Пролозі задіяні інші механізми. Завдання описується в термінах фактів і правил, а пошук рішення Пролог бере на себе у вигляді вбудованого механізму логічного висновку.

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

Пролог реалізований практично для всіх відомих операційних системта платформ. До операційних систем входять OS для мейнфреймів, все сімейство Unix, Windows, OS для мобільних платформ.

Багато сучасних реалізації мови мають внутрішнє розширення за рахунок ООП-архітектури. Крім пропрієтарних рішень, існують вільні реалізації Прологу.

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

Основні віхи розвитку мови Prolog

Prolog став втіленням ідеї використання логіки як мови програмування, яка зародилася на початку 1970-х років, і сама його назва є скороченням від слів “programming in logic” (програмування у термінах логіки). Першими дослідниками, які зайнялися розробкою цієї ідеї, були Роберт Ковальські (Robert Kowalski) з Едінбурга (теоретичні основи), Маартен ван Емден (Maarten van Emden) з Едінбурга (експериментальна демонстраційна система) та Ален Колмерое (Alain Colmerauer) з Марселя . Популяризації мови Prolog багато в чому сприяла ефективна реалізація цієї мови в середині 1970-х років Девідом Д. Г. Воррен (David D.H. Warren) з Единбурга. До нових досягнень у цій галузі відносяться засоби програмування на основі логіки обмежень (Constraint Logic Programming - CLP), які зазвичай реалізуються у складі системи Prolog. Кошти CLP показали себе практично як винятково гнучкий інструмент на вирішення завдань складання розкладів і планування матеріально-технічного постачання. А в 1996 був опублікований офіційний стандарт ISO мови Prolog.

Найбільш помітні тенденції історії розвитку мови Prolog

У розвитку мови Prolog спостерігаються дуже цікаві тенденції. Ця мова швидко набула популярності в Європі як інструмент практичного програмування. У Японії навколо мови Prolog було зосереджено всі розробки комп'ютерів п'ятого покоління. З іншого боку, у США ця мова загалом була прийнята з невеликим запізненням у зв'язку з деякими історичними причинами. Одна з них полягала в тому, що Сполучені Штати спочатку познайомилися з мовою Microplanner, яка також була близька до ідеї логічного програмування, але неефективно реалізована. Певна частка низької популярності Prolog у цій країні пояснюється також реакцією на існуючу спочатку "ортодоксальну школу" логічного програмування, представники якої наполягали на використанні чистої логіки і вимагали, щоб логічний підхід не був "заплямований" практичними засобами, що не належать до логіки. У минулому це призвело до поширення невірних поглядів на мову Prolog. Наприклад, деякі вважали, що цією мовою можна програмувати тільки міркування з висновком від цілей до фактів. Але істина полягає в тому, що Prolog - універсальна мова програмування і нею може бути реалізований будь-який алгоритм. Далека від реальності позиція “ортодоксальної школи” була подолана практиками мови Prolog, які прийняли прагматичніший підхід, скориставшись плідним об'єднанням нового, декларативного підходу з традиційним, процедурним.

Елементи синтаксису:

Коментар до кінця рядка	%
Реєстрозалежність	так
Регулярний вираз ідентифікатора змінної	[_A-Z][_a-zA-Z0-9]*
Регулярний вираз ідентифікатора функції	[_a-z][_a-zA-Z0-9]*
Привласнення значення змінної	is
Оголошення змінної	= або:-
Угруповання виразів	(...)
Тотожна рівність	==
Тотожна нерівність	\==
Порівняння	@< @=< @> @>=
Виклик функції	f(a,b,...)
Виклик функції без установок	f
Послідовність	,
Якщо - то - інакше	(A -> B; C)
Цикл із постумовою	repeat, ..., condition

Приклади:

Hello, World!:

Приклад для версій Visual Prolog 7.2

Visual Prolog створює проекти автоматично. Для запуску прикладу слід створити новий проект, обравши "Console" як UI Strategy, перейти до редагування файлу main.pro і замінити його вміст наведеним кодом.

implement main open core constants className = "main" . classVersion = "". clauses classInfo (className, classVersion). clauses run ():- console : : init (), stdio : : write ("Hello, World!" ), programControl:: sleep (1000 ), succeed (). end implement main goal mainExe:: run (main : :run ).

Факторіал:

Приклад для версій Visual Prolog 7.2

У main.cl додано один рядок factorial: (integer N, integer F) procedure (i,o). , Яка визначає бінарний предикат factorial з відомим першим та невідомим другим аргументами. Ключове слово procedure описує поведінку предикату, вказуючи, що його обчислення завжди буде успішним і буде знайдено одне рішення, так що відкати не знадобляться.

У main.pro знаходиться власне визначення нового предикату. Для кожного його виклику є дві можливі відповідності – з нульовим чи довільним першим аргументом. Visual Prolog перебирає формули порядку їх появи у коді, отже якщо перший аргумент дорівнює нулю, перевірка починається з першої формули factorial(0,F) . Перше правило формули — !, так зване відсікання, використання якого запобігає відкату до другої формули і таким чином забезпечує наявність рівно одного рішення предикату. Після цього змінна F, що містить рішення предикату, встановлюється 1 і виводиться на друк. Друга формула factorial(N,F) рекурсивно обчислює F1 як факторіал N-1, встановлює рішення предикату рівним N*F1 та виводить його на друк. Нарешті, stdio::nl друкує новий рядок.

При виконанні основної програми предикат factorial виконується рівно один раз для N=12. З кожним викликом рекурсії N зменшується на одиницю, доки не дорівнює нулю. Після цього значення факторіалів повертаються та виводяться на друк у порядку зростання. Програма обробляє лише чинники до 12!, т.к. спроба обчислення 13! викликає помилку переповнення цілого типу.

% main.cl class main open core predicates classInfo : core : :classInfo . factorial : (integer N , integer F ) procedure (i , o ). predicates run:core::runnable. end class main % main.pro implement main open core constants className = "main" . classVersion = "". clauses classInfo (className, classVersion). factorial (0 , F ) :- !, F = 1 , stdio : : write ("0! = 1" ), stdio : :nl . factorial (N , F ) :- factorial (N - 1 , F1 ), F = N * F1 , stdio : : write (N , "! = " , F ), stdio : :nl . clauses run ():- console : : init (), factorial (12 , F ), programControl:: sleep (1000 ), succeed (). end implement main goal mainExe:: run (main : :run ).

Числа Фібоначчі:

Приклад для версій Visual Prolog 7.2

У цьому прикладі визначаються два нові предикати — бінарний fibonacci(N,F) для обчислення N-ого числа Фібоначчі та loop(N) для його виведення на друк. Один раз обчислені числа не зберігаються для пізнішого використання, тому ця реалізація неефективна.

Слід зазначити відмінність реалізацій предикатів від прикладу факторіалу: формули, що описують початкові умови, задаються для довільного значення змінної, але обчислюються до кінця тільки в тому випадку, якщо перше правило (N<3 или N=1 , соответственно) оценивается как истинное. Кроме того, каждый предикат записан как одна формула, использующая конъюнкцию и дизъюнкцию, а не как набор отдельных формул, использующих только конъюнкцию.

% main.cl class main open core predicates classInfo : core : :classInfo . fibonacci : (integer N , integer F ) procedure (i , o ). loop: (integer N) procedure (i). predicates run:core::runnable. end class main % main.pro implement main open core constants className = "main" . classVersion = "". clauses classInfo (className, classVersion). fibonacci (N , F ) :- N< 3 , !, F = 1 ; fibonacci (N - 1 , F1 ), fibonacci (N - 2 , F2 ), F = F1 + F2 . loop (N ) :- ( N = 1 , !, fibonacci (1 , F ); loop (N - 1 ), fibonacci (N , F ) ), stdio : : write (F , ", " ). clauses run ():- console : : init (), loop (16 ), stdio : : write ("..." ), programControl:: sleep (1000 ), succeed (). end implement main goal mainExe:: run (main : :run ).

Hello, World!:

Приклад для версій B-Prolog 7.4-3, ECLiPSe CLP 6.0 #188, Poplog 15.5 (Prolog), gprolog 1.3.0, swipl 5.6.x

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

Hello, World!
yes

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

Слід зазначити, що заміна одинарних лапок на подвійні виводить рядок як масив ASCII-кодів окремих символів:

| ?- write("Hello, World!").

write ("Hello, World!"), nl.

Числа Фібоначчі:

Приклад для версій Poplog 15.5 (Prolog)

Проста рекурсивна реалізація надто неефективна з точки зору пам'яті, щоб успішно виконуватись у Poplog, тому цей приклад демонструє складнішу техніку – рекурсію із запам'ятовуванням. Додатковий предикат memo(Goal) визначається так, що вперше, коли оцінюється Goal результат оцінки додається в базу фактів, і при наступному запиті не переоцінюється, а використовується як відомий факт.

Після цього предикат fib(N,F) визначається рекурсивно, але кожен виклик fib "обернуті" в предикат memo тому для кожного значення N fib(N,F) оцінюється тільки один раз. При такому підході друк обчислених чисел може здійснюватися відразу після їх обчислення без додаткового циклу.

% fibonacci.pl :- dynamic (stored / 1). memo (Goal): - stored (Goal) -> true; Goal, assertz (stored (Goal)). fib (1 , 1 ) :- !, write ("1, "). fib (2, 1): -!, write ("1,"). fib (N , F ) :- N1 is N - 1 , memo (fib (N1 , F1 )), N2 is N - 2 , memo (fib (N2 , F2 )), F is F1 + F2 , write (F ) , write (", "). % interactive [-fibonacci]. fib (16, X), write ("..."), nl.

Факторіал:

Приклад для версій Poplog 15.5 (Prolog)

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

[-fact]. завантажує базу фактів та правил з цього файлу у поточну сесію Poplog (і виводить повідомлення fact reconsulted , щоб позначити успішність завантаження). Запит fact(16,X). намагається знайти значення X, у якому цей предикат буде оцінено як істинний. Висновок, який потрібний у прикладі, буде побічним ефектом оцінювання запиту, а основним результатом буде X = 20922789888000? . Це означає, що якщо ви незадоволені такою прив'язкою змінних, ви можете відмовитися від неї (ввівши;) і буде продовжено пошук кращої прив'язки.

% fact.pl fact (X , F ) :- ( X = 0 , F = 1 ; Y is X - 1 , fact (Y , Z ), F is X * Z ), write (X ), write ("! = "), write (F), nl. % interactive [-fact]. fact (16, X).

Квадратне рівняння:

Приклад для версій Visual Prolog 7.2

Для запуску створіть новий проект з UI Strategy “Console” та замініть вміст файлів main.cl та main.pro наведеним кодом.

У main.cl додано один рядок q: () procedure(). . Ключове слово procedure описує поведінку предикату, вказуючи, що його обчислення завжди буде успішним і буде знайдено одне рішення, так що відкати не знадобляться.

У main.pro знаходиться власне визначення нового предикату. Предикат q не приймає аргументів, оскільки читає необхідні дані stdio . Умовне оцінювання (конструкція if-then-else) працює так само, як в інших мовах. Єдиною відмінністю є знак відсікання! перед then . Це означає, що як тільки умова if виконується, відкат не буде потрібно.

Хитрість цього прикладу в тому, що неможливо одразу обчислити дискримінант, як у інших мовах. Тип даних за умовчанням для змінної D у присвоєнні D = B*B-4*A*C - uReal , який може зберігати лише негативні числа.

% main.cl class main open core predicates classInfo : core : :classInfo . q : () procedure (). predicates run:core::runnable. end class main % main.pro implement main open core constants className = "main" . classVersion = "". clauses classInfo (className, classVersion). q () :- stdio : : write ("A = "), A = stdio : : read (), if (A = 0 ), ! then stdio : : write ("Not a quadratic equation." ), stdio : :nl else stdio : : write ("B = " ), B = stdio : : read (), stdio : : write ("C = " ) , C = stdio : : read (), якщо (B * B = 4 * A * C ), ! then stdio : : writef ("x = %f" , - B / 2 . 0 / A ) elseif (B * B > 4 * A * C ), ! then D = B * B - 4 * A * C , stdio : : writef ("x1 = %f\n" , (- B + math : : sqrt (D )) / 2 . 0 / A ), stdio : : writef ("x2 = %f" , (- B - math :: sqrt (D )) / 2 . 0 / A ) else D = - B * B + 4 * A * C , stdio :: : writef ("x1 = (%f, %f)\n" , - B / 2 . 0 / A , math : : sqrt (D ) / 2 . 0 / A , stdio : : writef ("x2 = (%f, %f) " , - B / 2 . 0 / A , - math : : sqrt ( D ) / 2 . 0 / A ) end if end if . clauses run():- console : : init(), q(), succeed (). end implement main goal mainExe:: run (main : :run ).

Факторіал:

Приклад для версій B-Prolog 7.4-3, gprolog 1.3.0, swipl 5.6.x

Як у GNU Prolog, так і в B-Prolog 12! не міститься в цілісний тип даних, тому всі значення після 11! неправильні. У SWI-Prolog переповнення немає.

Результат для GNU Prolog: compiling /home/nickolas/Desktop/progopedia/prolog/fact.pl for byte code…
/home/nickolas/Desktop/progopedia/prolog/fact.pl compiled, 3 lines read - 1372 bytes written, 5 ms

Результат B-Prolog: consulting::fact.pl

`| ? - fact (16, X).

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = -57869312
13! = -215430144
14! = 205203456
15! = -143173632
16! = -143294464

X = -143294464?

% fact.pl fact (X , F ) :- ( X = 0 , F = 1 ; Y is X - 1 , fact (Y , Z ), F is X * Z ), write (X ), write ("! = "), write (F), nl. % interactive [fact]. fact (16, X).

Числа Фібоначчі:

Приклад для версій B-Prolog 7.4-3, gprolog 1.3.0, swipl 5.6.x

Приклад майже ідентичний прикладу , крім синтаксису підключення файла.

% fibonacci.pl :- dynamic (stored / 1). memo (Goal): - stored (Goal) -> true; Goal, assertz (stored (Goal)). fib (1 , 1 ) :- !, write ("1, " ). fib(2 , 1 ) :- !, write("1, " ). fib(N, F) :- N1 is N- 1 , memo(fib(N1, F1)), N2 is N- 2 , memo(fib(N2, F2)), F is F1 + F2, write(F), write(", " ). % interactive [ fibonacci]. fib(16 , X), write("..." ), nl.

Квадратне рівняння:

Приклад версії gprolog 1.3.0

read_integer - не стандартний предикат, а розширення GNU Prolog, тому цей приклад не працюватиме в інших реалізаціях.

q :- write("A = "), read_integer(A), ( A = 0 , write("Not a quadratic equation"); write("B = "), read_integer(B), write("C = "), read_integer(C), D is B* B- 4 * A* C, ( D = 0 , write("x="), X is - B/ 2 / A, write(X); D > 0 , write("x1 = "), X1 is (- B+ sqrt(D)) / 2 / A, write(X1), nl, write("x2 = "), X2 is (- B- sqrt(D)) / 2 / A, write(X2); R is - B/ 2 / A, I is abs(sqrt(- D) / 2 / A), write("x1 = ("), write(R), write(", " ), write(I), write(")" ), nl, write("x1 = ("), write(R), write(", -" ), write(I), write(")" ) ) ).

Квадратне рівняння:

is B* B- 4 * A* C, ( D = 0 , write("x="), X is - B/ 2 / A, write(X); D > 0 , write("x1 = "), X1 is (- B+ sqrt(D)) / 2 / A, write(X1), nl, write("x2 = "), X2 is (- B- sqrt(D)) / 2 / A, write(X2); R is - B/ 2 / A, I is abs(sqrt(- D) / 2 / A), write("x1 = ("), write(R), write(", " ), write((N, F) :- N > 0 , N1 is N - 1 , factorial(N1, F1), F is N * F1. main :- ( for(N, 0 , 16 ) do factorial(N, F), write(N), write("! = " ), write(F), nl ). (N1, F1), fibonacci(N2, F2), F is F1 + F2. main :- ( for(N, 1 , 16 ) do fibonacci(N, F), write(F), write(", " ) ), writeln("..." ).

Числа Фібоначчі:

Приклад для версій ECLiPSe CLP 6.0 #188

Числа Фібоначчі обчислюються рекурсивно, у своїй використовується мемоізація, реалізована з допомогою ECLiPSe-специфічного механізму store .

Для організації циклу у предикаті main використовується специфічна для ECLiPSe ітеративна керуюча структура(Мета-предикат) for .

:- local store(fibonacci). fibonacci(1 , 1 ) :- !. fibonacci(2 , 1 ) :- !. fibonacci(N, F) :- N > 2 , ( % використовуємо збережений результат store_get(fibonacci, N, F), ! ; N1 is N - 1 , N2 is N - 2 , fibonacci(N1, F1), fibonacci(N2, F2), F is F1 + F2, store_set(fibonacci, N, F) % зберігаємо отриманий результат ). main :- ( for(N, 1 , 16 ) do fibonacci(N, F), write(F), write(", " ) ), writeln("..." ).

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

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

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

Логіка предикатів була розроблена для найпростішого перетворення принципів логічного мислення в форму, що записується. Пролог використовує переваги логіки синтаксису для розробки програмної мови. У логіці предикатів ви перш за все виключаєте зі своїх пропозицій всі несуттєві слова. Потім ви перетворюєте ці пропозиції, ставлячи в них на перше місце відношення, а після нього згруповані об'єкти. Надалі об'єкти стають аргументами, між якими встановлюється це ставлення. Як приклад у табл. представлені пропозиції, перетворені відповідно до синтаксису логіки предикатів.

Таблиця 1.Синтаксис логіки предикатів

2. Факти

На Пролозі описуються об'єкти (objects) та відносини (relations), а потім описує правила (rules), у яких ці відносини є істинними. Наприклад, пропозиція

Біл любить собак. (Billlikesdogs.)

встановлює відношення між об'єктами Bill та dogs (Білл та собаки); цим ставленням є likes (любить). Нижче наведено правило, що визначає, коли пропозиція "Білл любить собак" є істинною:

Білл любить собак, якщо собаки добрі. (Bill likes dogs if the dogs are nice.)

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

Нижче представлено кілька пропозицій природною мовою з відношенням "любить" (likes):

Білл любить Сінді. (Bill likes Cindy)

Сінді любить Білла. (Cindy likes Bill)

Біл любить собак. (Bill likes dogs)

А тепер перепишемо ці ж факти, використовуючи синтаксис Прологу:

likes(bill, cindy).

likes(cindy, bill).

likes (bill, dogs).

Факти, окрім відносин, можуть виражати й якості. Так, наприклад, пропозиції природної мови "Kermitisgreen" (Керміт зелений) та "Caitlinisgirl" (Кейтлін - дівчинка) на Пролозі, виражаючи ті ж властивості, виглядають так:

3. Предикати

Ставлення у Пролозі називається предикатом. Аргументи- це об'єкти, що пов'язуються цим ставленням; у факті

likes (bill, cindy).

відношення likes – це предикат, а об'єкти bill та cindy – аргументи.

Приклади предикатів з різним числом аргументів:

pred(integer, symbol)

person (last, first, gender)

birthday(firstName, lastName, date)

У прикладі показано, що предикати можуть не мати аргументів.

4. Правила

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

Сінді любить все, що любить Білл. (Cindy likes everything that Bill likes)

Кейтлін любить усе зелене. (Caitlin likes everything that is green)

Використовуючи ці правила, ви можете з попередніх фактів знайти деякі речі, які люблять Сінді та Кейтлін:

Сінді любить Сінді. (Cindy likes Cindy)

Кейтлін любить Керміт. (Caitlin likes Kermit)

Щоб перекласти ці правила на Пролог, вам потрібно трохи змінити синтаксис:

likes(cindy, Something): - likes (bill, Something). ilikes(caitlin, Something): - green (Something) .

Символ:- має сенс "якщо", і служить для поділу двох частин правила: заголовка та тіла.Можна розглядати правило як процедуру. Іншими словами, правила

likes(cindy, Something): - likes (bill, Something).

likes(caitlin, Something): - green (Something).

означають: "Щоб довести, що Сінді любить щось, доведіть, що Білл любить це"і" Щоб довести, що Кейтлін любить щось, доведіть, що це щось зелене.. З такого "процедурного" погляду правила можуть "попросити" Пролог виконати інші дії, відмінні від доказів фактів, наприклад, надрукувати що-небудь.

5. Запити (Цілі)

Описавши в Пролозі кілька фактів, можна ставити питання стосовно відносин між ними. Це називається запитом(query) системи мови Пролог. Можна пропонувати такі ж питання, які ми могли б поставити вам про ці відносини. Грунтуючись на відомих, заданих раніше фактах і правилах, ви можете відповісти на питання про ці відносини, так само це може зробити Пролог. На природній мові ми запитуємо: Does Bill like Cindy ? (Білл любить Сінді?)За правилами Прологу ми запитуємо:

likes(bill, cindy).

Отримавши такий запит, Пролог відповість:

тому що Пролог має факт, що підтверджує, що це так. Трохи ускладнивши питання, можна запитати природною мовою: What does Bill like ? (Що любить Білл?)За правилами Прологу ми запитуємо:

likes(bill, What).

Необхідно відзначити, що другий об'єкт – What – починається з великої літери, тоді як перший об'єкт – bill – ні. Це тому, що bill - фіксований, постійний об'єкт - відома величина, aWhat - змінна.

Змінні завжди починаються з великої літери або символу підкреслення!

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

Так, як йому відомо, що

likes(bill, cindy).

likes(bill, dogs) .

Якби ми запитали:

What does Cindy like? (Що любить Сінді?)

likes(cindy, What).

то Пролог відповів би:

оскільки Пролог знає, що Сінді любить Білла, і що Сінді любить те саме, що й Білл, і що Білл любить Сінді та собак.

Ми могли б поставити Прологу та інші питання, які можна поставити людині. Але питання на кшталт "Яку дівчину любить Білл?" не отримають рішення, тому що прологу в даному випадку не відомі факти про дівчину, а він не може вивести висновок, заснований на невідомих даних: у цьому прикладі ми не дали прологу будь-якого відношення або властивості, щоб визначити, чи є які або об'єкти дівчатами.

6. Розміщення фактів, правил та запитів

Припустимо, є такі факти та правила:

Швидка машина – приємна. (Afastcarisfun).

Велика машина – гарна. (A big car is nice).

Маленька машина – практична. (A little car is practical).

Біллу подобається машина, якщо вона приємна. (Bill likes a car if the car is fun).

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

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

likes(ellen, tennis).

likes (John, football).

likes (torn, baseball).

likes (eric, swimming).

likes (mark, tenis).

likes (bill, Activity): - likes (torn, Activity).

Останній рядок у програмі є правилом. Це правило відповідає пропозиції природної мови:

Біллу подобається заняття, якщо Тому подобається це заняття. (Bill likes an activity if Tom likes that activity)

У цьому правилі заголовок - це likes (bill, Activity), а тіло - likes (torn, Activity). Зауважимо, що в цьому прикладі немає фактів про те, що Біл любить бейсбол. Щоб з'ясувати, чи любить Білл бейсбол, можна надати Прологу такий запит:

likes (bill, baseball).

Намагаючись знайти рішення з цього запиту, Пролог використовуватиме правило:

Завантажте програму ch02e01.pro у середу візуальної розробки VisualProlog та запустіть її утилітою TestGoal .

likes(symbol,symbol)

likes(ellen, tennis).

likes(John,football).

likes(torn,baseball).

likes(eric, swimming).

likes(mark,tennis).

likes(bill,Activity):-likes(torn, Activity).

likes(bill, baseball).

Утиліта TestGoal відповість у вікні програми:

Система використовувала комбіноване правило

likes (bill, Activity): - likes (torn, Activity).

likes(torn, baseball). для вирішення, що likes(bill, baseball).

Спробуйте також наступний запит у GOAL-розділі:

likes (bill, tennis).

Утиліта Test Goal відповість:

оскільки:

· немає фактів, які кажуть, що Біл любить теніс;

· Відношення Білла до тенісу не може бути логічно виведено з використанням цього правила та наявних фактів.