Число аргументів предикату
називається арністю предикату. Пролог
допускає предикати з однаковою назвою,
але різною арністю.
Пролог проводить автоматичне
перетворення доменів:
1) між рядками і символами;
2) між цілим, символьним
і дійсним доменом.
Як ми вже зазначали, синтаксис
правила складається з трьох частин:
голова: - <підціль>, <підціль>,
... , <підціль>.
Кожна підціль викликає відповідний
предикат Прологу. Пролог-система тестує
викликаний предикат і перевіряє, чи може
він задовольнитися. Якщо поточна підціль
буде задоволена, тоді виклик справджується
й обробка переходить до наступної підцілі.
Коли обробка успішно досягла крапки,
то кажуть, що правило істинне.
У разі, якщо якась із підцілей
завершується невдачею, тоді Пролог-система
повертається назад і переглядає альтернативи
попередньо переглянутих підцілей, але
з уже іншими значеннями параметрів. Цей
процес називається бектрекінгом.
Ви можете включити в програму
деякі директиви комп’ютера безпосередньо
або ж зробити це, вибравши пункт меню
Options /CompilerDirectives. Наприклад, директиву
include. За її допомогою можна підключити
до програми написані попередньо процедури.
Додамо рядок include “my.pro” на початок програми.
А у файлі my.pro описуються процедури, які
використовуються у програмі розв’язку
задачі. Якщо розглянутий шлях не дає відповіді,
необхідно переглянути альтернативний.
Такий підхід дістав назву бектрекінг.
Пролог реалізує бектрекінг
таким чином: на початку пошуку розв’язання
поставленої проблеми він ставить маркер
на місце проглядання та вибирає першу
підціль. Якщо її розв’язання завершиться
невдачею, тоді Пролог повертається до
точки, відміченої маркером і намагається
знайти альтернативну підціль. При поверненні
в точку бектрекінгу, він звільнює усі
змінні, зв’язані після входу в дану точку.
Розглянемо програму:
domains
name, thing = symbol
predicates
likes(name, thing)
reads(name)
is_inquisitive(name)
clauses
likes(john, wine).
likes(lance, skiing).
likes(Z,books) :-reads(Z),
is_inquisitive(Z).
likes(lance, books).
likes(lance, films).
reads(john).
is_inquisitive(join).
Задамо системі запитання у
вигляді мети, яка складається з двох підцілей:
likes(X,wine), likes(X,books)
Пролог починає виведення згідно
з основним принципом бектрекінгу. Підцілі
повинні задовольнятися послідовно зверху
вниз.
Пролог визначає яка підціль
буде використовуватись для задоволення
відповідного фрагменту предикату згідно
з другим принципом бектрекінгу. Фрагменти
предикату розглядаються в тому порядку,
в якому вони розміщені в програмі - послідовно
зверху вниз.
Підціль likes(X, wine) відповідає
факту likes(john, wine). Тому Х зв’язується з
john. Потім Пролог робить спробу задовольнити
наступну підціль справа. Виклик другої
підцілі розпочинає новий пошук з Х = john.
Перший пункт likes(john,wine) не відповідає підцілі
likes(X,books), тому що wine не є тим же, що й books.
Тому Пролог намагається підібрати наступний
пункт. Подальший пошук визначається третім
правилом бектрекінгу. Коли підціль відповідає
голові, тоді наступним повинно задовольнятися
тіло даного правила. Тіло правила у свою
чергу створює нові підцілі, котрі повинні
бути задоволені.
І нарешті, четвертий принцип
бектрекінгу такий. Мету буде задоволено,
коли будуть знайдені відповідні факти
для кожного рівня дерева мети.2
Бектерінг з внутрішньою метою
ілюструється програмою:
predicates
type(symbol, symbol)
is_a(symbol, symbol)
lives(symbol, symbol)
can_swim(symbol)
goal
can_swim(What) ,
write("A ", What, " canswim.").
clauses
type(ungulate, animal).
type(fish, animal).
is_a(zebra, ungulate).
is_a(herring, fish).
is_a(shark,fish).
lives(zebra, on_land).
lives(frog, on_land).
lives(frog,in_water).
lives(shark, in_water).
can_swim(Y) :-
type(X, animal) ,
is_a(Y, X) , lives(Y,in_water).
1.5. Синтаксис мови
програмування Prolog
Для кодування алгоритму мовою
програмування необхідно знати синтаксис
мови, тобто його основні оператори, типи
змінних й ін. Команди й різні типи алгоритмічних
структур реалізуються мовою програмування
за допомогою операторів. Кожен оператор
має свій формат.
У формат операторів, крім ключових
слів, входять змінні й арифметичні вираження.
Змінні бувають різних типів, тип змінної
визначає, які значення може приймати
ця змінна.
Команда – формат оператора;
Введення - даних INPUT< список
змінних>;
Команда – PRINT<список змінних>;
Присвоювання – LET<змінна>
= <арифметичне вираження>;
Команда розгалуження – IF <умова>
THEN <оператори> ELSE <оператори>;
Команда циклу - <оператори>NEXT<змінна>;
Команда циклу – FOR<змінна>FROM<арифметичне
вираження>TO<арифметичне вираження>.
Арифметичні вираження можуть
містити в собі: числа, змінні, знаки арифметичних
виражень, стандартні функції й круглі
дужки.
Мова програмування характеризується
властивими йому механізмами керування
й обробки даних. Пролог як універсальну
мову програмування можна розглядати
й із цих точок зору. При успішному виконанні
обчислення засобу керування програм
мовою Пролог подібний до засобів керування
у звичайних процедурних мовах. Звертання
до деякої мети відповідає виклику процедури,
порядок цілей у тілі правила відповідає
послідовності операторів. Точніше, правило
А В1,В2,…,Вn можна розглядати як визначення
процедури:
Procedure A
Call B1
Call B2
.
.
.
CallBn
End.
Рекурсивний виклик мети в Пролозі
в послідовності дій й у реалізації подібний
тому ж виклику у звичайних рекурсивних
мовах. Розходження виникає при реалізації
повернення. У звичайних мовах, якщо обчислення
не може бути продовжене (наприклад, всі
галузі в операторі case помилкові), виникає
помилка виконання. У Пролозі обчислення
просто повертається до останнього вибору
й робиться спроба продовжити обчислення
новим чином.
Структури даних, якими оперують
логічні програми, – терми – відповідають
загальним структурам записів у звичайних
мовах програмування. Пролог використовує
дуже гнучку систему організації структур
даних. Подібно мові Лісп, Пролог є без
типовою мовою, що не містить оголошення
даних.
Інші особливості використання
структур даних у мові Пролог пов’язані
із природою логічних змінних. Логічні
змінні співвідносяться з об’єктами,
а не з комірками пам’яті. Якщо змінній
зіставлений конкретний об’єкт, то ця
змінна вже ніколи не може посилатися
на інший об’єкт. Іншими словами, логічне
програмування не підтримує механізм
деструктивного присвоювання, що дозволяє
змінювати значення ініціалізованої змінної.
У логічному програмуванні
обробка даних повністю укладена в алгоритмі
уніфікації. В уніфікації реалізовані:
- однократне присвоювання,
- передача параметрів,
- розміщення записів,
- доступ до полів записів для
одночасних читання/запису.
Традиційні мови, як правило,
містять різного ступеня складності засоби
обробки помилкових і виняткових ситуацій.
Чистий Пролог не містить механізм обробки
помилок і виняткових ситуацій, вбудованих
в опис мови. На відміну від традиційних
мов ситуації, що призводять до помилки
(наприклад, відсутність потрібної галузі
в операторі case, розподіл на нуль), у чистому
Пролозі призводять до “відмови”.
Основна мета логічного програмування
– створити можливість розробки програм
мовою високого рівня. В ідеалі програміст
повинен записати аксіоми, що визначають
необхідніші відносини, повністю ігноруючи,
яким образом ці аксіоми будуть використатися
в процесі виконання. Наявні мови логічного
програмування, і, зокрема Пролог, усе
ще далекі від цього ідеалу декларативного
програмування. Не можна ігнорувати конкретний,
чітко певний спосіб моделювання абстрактного
оператора в реалізації кожної мови. Ефективне
логічне програмування вимагає знання
й використання цього способу.3
Висновки до І розділу
У практичному програмуванні
на Пролозі необхідно звернути увагу на
ефективність програм. Встановимо критерії
оцінки програм. Основний оцінюваний параметр
– число виконуваних уніфікацій і число
спроб уніфікації в процесі обчислення.
Цей параметр пов’язаний із часом роботи
програми. Ще один параметр – глибина
вкладеної рекурсії. Якщо в процесі обчислень
глибина стане більш максимально припустимої,
то обчислення перервуться. На практиці
ця проблема є основною. Третій параметр
– число породжених структур даних.
Можна припустити, що при розумному
записі детермінованого послідовного
алгоритму у вигляді програми на Пролозі
очікувана ефективність алгоритму збережеться.
Звичайно результуючі програми на Пролозі
не ґрунтуються на уніфікація загального
виду або глибоких повернень.
Складності можуть виникнути
при реалізації алгоритмів, пов’язаних
з істотною перебудовою структур даних,
наприклад використовуючи дерева; при
цьому витрати будуть зростати логарифмічно.
Однак у багатьох випадках більш природно
було б модифікувати сам алгоритм, пристосовуючи
його до принципу однократного присвоювання,
властивому логічним змінним.
ІІ. Розв’язування
математичних задач мовою Prolog
Пролог – мова, що швидко розвивається.
За останні роки з’явилося більше десятка
його нових діалектів; розроблені об’єктні
розширення Прологу, в якому є засоби для
роботи з абстрактними типами даних. Виявилося,
що на Пролозі можливе розв’язання задач
з використанням підходів, далеких від
математичної логіки, зокрема, функціонального
і об’єктно-орієнтованого програмування.
Пролог, який відноситься до
реляційних мов високого рівня, суттєво
відрізняється від процедурних мов програмування
(Бейсик, Паскаль, Фортран тощо) як за типами
даних, так і за базовими конструкціями,
та розрахований на ефективне розв’язання
широкого кола задач певного класу, реалізація
яких процедурними мовами значно ускладнюється.
Але Пролог не є універсальною мовою програмування,
тому існує ряд класів задач, для розв’язку
яких використання Прологу є малоефективним.
До таких задач слід віднести обчислювальні
задачі: засоби виконання обчислювальних
дій Прологу досить слабкі і носять переважно
допоміжний характер.
Пролог придатний для задач,
де головне значення мають складно структуровані
нечислові дані, а також для задач, де важливу
роль відіграє пошук розв’язку серед
багатьох варіантів.
Процес розв’язання задачі
мовою програмування Prolog проходить у декілька
етапів:
- Аналізуються дані умови задачі
(або ще кажуть, предметна область): факти,
функції, відношення. Вибираються позначення
для них.
- Описуються природною мовою
з точки зору істинності відношення та
функції.
- Описані відношення оформлюються
як аксіоми у вигляді фраз (фактів, правил),
зрозумілих Прологу для роботи з ними.
Множина таких фраз складає структуру
предметної області. Програма вводиться
у робоче поле компілятора.
- Формулюються та виконуються
запити до введеної програми, завдяки
чому досягається результат розв’язку
задачі.
- Розв’язування логічних
задач
Приклади деяких логічних задач
мовою Prolog:
Приклад1.
Написати та реалізував програму
встановлення родинних зв'язків: Василь
має дочку Ольгу, у якої два сини Михайло
і Максим. Використовувати зовнішні і
внутрішні цілі.
domains
name = symbol
divdicates
men (name)
mama (name)
sons (name, name)
doughter (name, name)
deda (name, name)
brother (name, name).
goal
doughter (Z, Y),
write (Z, Y),
nl.
clauses
men ("Vaciliy").
men ("Michail").
men ("Maxim").
mama ("Olga").
sons ("Michail", "Olga").
sons ("Maxim", "Olga").
doughter ("Olga", "Vasiliy").
deda (X, Y): - men (X), men (Y), sons (X, Y), doughter
(Z, Y).
brother (X, Y): - men (X), men (Y), sons (X, Z),
sons (Y, Z), X <> Y.
Результат: Olga, Vaciliy
Приклад 2.Написати програму, що створює
список міст. Виконати програму з різними
внутрішніми і зовнішніми цілями.
domains
town_list = town
town = symbol
divdicates
towns (town_list)
goal
towns ([A, B, C, D, E]),
write (A ,",", B ,",", C ,",",
D ,",", E).
clauses
towns (["Kazan", "Nignekamsk",
"Elabuga", "Bugulma", "Almetevsk"]).
Результат: Kazan, Nignekamsk, Elabuga, Bugulma,
Almetevsk
Приклад 3. Hello, World! - Prolog:
Visual Prolog створює проекти автоматично
. Для запуску прикладу слід створити новий
проект, вибравши "Console" як UIStrategy,
перейти до редагування файлу main.pro і замінити
його вміст наведеними кодом.
implement main
open core
constants
class Name = "main".
Class Version = "".
clauses
clas sInfo Cclass Name, class Version).
clauses
run():-
console::init(),
stdio::write("Hello, World!"),
program Control::sleep(1000),
succeed(). end implement main
goal
mainExe::run(main::run)
Приклад 4. Відомо те, що Петро та Ольга
навчаються у десятому класі, Хома та Леся
– у 9 класі. Один учень знає іншого, якщо
вони вчаться в одному класі. Вважається,
що певний учень не може знати сам себе.
domains
учень = symbol
клас = integer
predicates
вчиться (учень, клас)
знає (учень, клас)
clauses
вчиться (хома, 9).
вчиться (петро, 10).
вчиться (ольга, 10).
вчиться (леся, 9).
знає (X, Y) :-
вчится( Х, Клас),
вчиться (Y, Клас),
X<>Y.4
Коментар: у програмі оголошуються предикати вчиться/2 і знає/2, аргументи учень типу «рядок
символів» і клас типу «ціле
число». Умова того, що учень Х навчається
в одному і тому ж класі з учнем Y забезпечується
однаковим іменем змінної у відповідних
умовах правила.
- Розв’язування математичних
задач
Наведемо приклади математичних
задач, алгоритми розв’язання яких ви
знаєте:
• додавання двох багатоцифрових
чисел;
• ділення відрізка навпіл
за допомогою циркуля і лінійки;
• розв'язування квадратного
рівняння тощо.
Розглянемо декілька прикладів
розв’язування математичних задач мовою
Prolog.
- Числа Фібоначчі:
x Fibonacci.pl
:- dynamic(stored/1).
memo(Goal) ;-
stored(Goal) → true;
Goal, asserts(stored(Goal)).
fib(1,1) :- 1, write(‘1, ‘).
fib(2,1) :- 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(‘, ‘).
x interactive
[-fibonacci].