3.6. Логічне програмування
Для представлення даних використовуються терми і предикатні терми. Алгоритми представляються за допомогою аксіом і правил виведення. Елементарним кроком обчислень є уніфікація і підстановка.
Об’єкт, що співставляється логічній програмі, являє собою семантичну модель логічної системи, яку можна також розглядати як опис відповідної предметної області. Вхідні дані представляються за допомогою мови запитів. Кожний запит можна розглядати як систему логічних (алгебраїчних, якщо предикат рівності є одним із предикатів) рівнянь, а стратегія є стратегією пошуку розв’язків цих рівнянь. Стратегія для логічної мови визначає побудову дерева пошуку виведення. Для цієї парадигми існує набагато більше свободи при виборі способу розв’язку задач, ніж для інших парадигм, і тому практика логічного програмування породила цілий ряд спеціальних засобів для управління стратегіями. Як правило, ці засоби включаються в мову (наприклад, різні види оператора відтинання (cut-оператор)).
Логічна програма обчислення НСД. Для побудови логічної програми представимо бінарну функцію НСД у вигляді тернарного предиката НСД, який визначається таким чипом: НСД1 (x,y,z) = 1 ⇔ НСД(x, у) = z.
НСД1 (x,y,z).
begin
НСД1(х,x,x);
НСД1(х,y, z) : -(х > у)& НСД1(x -y,y,z)
НСД1(x, у, z) : - (х < у)& НСД1(x, у - x, z)
НСД1(
,
,
)?
- запит.
end
Однією із мов логічного програмування є Пролог.
При побудові програм Прологу використовується той же підхід, що й у предикативних логіках. Для опису предметної області ми трансформуємо речення природної мови, ставлячи на перше місце відношення.
Наприклад:
Японський автомобіль економний. -> економний(японський_автомобіль),
Вані подобається автомобіль, якщо він економний. ->
подобається (ваня,автомобіль) іf економний(автомобіль).
Програміст визначає об’єкти і відношення. Потім формулює правила про те, у якому разі ці відношення справджуються.
Правило , що визначає, коли речення
Вані подобається автомобіль
справджується, матиме вигляд:
Вані подобається автомобіль, якщо він економний.
У Пролозі зв’язок між об’єктом називається фактом. Факти можуть виражати як властивості , так і відношення:
економний (автомобіль), студент (Ваня).
Правила визначають які висновки можна зробити з даних правил.
Ми можемо задавати питання про пролог відношення у вигляді запитів. Пролог-система будує відповідь і виводить її до друку.
Наприклад, речення Що подобається Вані? Трансформується у запит
подобається (ваня,Що).
Правила Прологу складаються з трьох частин: голови, символу і тіла.
Наприклад, у правилі
can_buy(X, Y) :-
person(X),
car(Y),
likes(X, Y),
for_sale(Y).
can_buy(X, Y)- голова, :- символ, person(X), car(Y), likes(X, Y), for_sale(Y) - тіло.
Розглянемо програму:
predicates
can_buy(symbol, symbol)
person(symbol)
car(symbol)
likes(symbol, symbol)
for_sale(symbol)
clauses
can_buy(X, Y) :-
person(X),
car(Y),
likes(X, Y),
for_sale(Y).
person(kelly).
person(judy).
car(lemon).
car(hot_rod).
likes(kelly, hot_rod).
likes(judy, pizza).
for_sale(pizza).
for_sale(lemon).
for_sale(hot_rod).
До програми можна задати питання:
Що можуть купити judy i kelly?
can_buy(judi,X) can_buy(kelly,X).
Хто може купити бутерброд з гарячою сосискою? can_buy(X,hot_rod).
Розглянемо ще одну програму в PDC Prolog.
predicates
likes(symbol,symbol)
clauses
likes(ellen, reading).
likes(john, computers).
likes(john, badminton).
likes(leonard, badminton).
likes(eric, swimming).
likes(eric, reading).
Побудуємо запит:
Чи існує особа, яка любить читати і купатися?
likes(Person,reading) and likes(Person,swimming)
Відповіддю буде:
Person = eric
Solution