« Назад

Мета: Вивчення основ логічного програмування, основні принципи мови Prolog, включаючи пропозиції, предикати, змінні, цілі і зіставлення. Виконати одне із запропонованих завдань, оформити і захистити звіт, відповісти на контрольні запитання.

Хід роботи

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

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

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

Основні розділи Visual Prolog – програм

Зазвичай програма на Visual Prolog 7 складається з наступних основних програмних розділів:

− розділ core;

− розділ constants(констант);

− розділ domains (доменів);

− розділ class facts (фактів);

− розділ predicates (предикатів);

− розділ clauses (пропозицій);

− розділ goal (цілей).

Структуру програми на Visual Prolog 7 можна представити таким чином:

implement main (class draw)

open core

constants

domains

class facts

class predicates

clauses

end implement main (end class draw)

goal

 

1. Class (клас)

Оголошення класу здійснюється наступним чином: classclass_name (оголошення класу class_name) або

Implement class_name (оголошення класу, успадкованого від класу class_name).

Поки будемо використовувати оголошення класу, успадкованого від main:

implement main

В кінці класу використовується:

endclass_name        (закривається клас class_ name)

або

end implement class_name (закривається клас, успадкований

class_name).

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

end implement main

 

2. Розділ open

В розділ open вказуються необхідні бібліотеки.

Поки будемо використовувати тільки бібліотеку core. При необхідності можна підключити наступні бібліотеки:

- stdio

- string

- vpi

Наприклад, при підключенні бібліотеки stdio в коді програми замість stdio::write або stdio::read можна писати тільки write або read.

 

3. Розділ constants (констант)

У програмах на Visual Prolog можна оголошувати і використовувати символічні константи. Розділ для оголошення констант позначається ключовим словом constants, за яким слідують самі оголошення, що використовують наступний синтаксис:

<Id> = < макровизначення >

<Id> – ім'я символічної константи, а < макровизначення > - це те, що Ви привласнюєте цій константі. Кожне <Макровизначення> завершується символом нового рядка і, отже, на одному рядку може бути тільки один опис константи. Оголошені таким чином константи можуть пізніше використовуватися в програмах.

Наприклад:

Перед компіляцією програми Visual Prolog замінить кожну константу на відповідний їй рядок.

На використання символічних констант накладаються наступні обмеження:

- Опис константи не може посилатися сам на себе:

my_number = 2*my_number/2 % не допускається

Це призведе до повідомлення про помилку "Recursive declatation `name_of_constant`»;

- В описах констант система не розрізняє верхній і нижній регістри. Отже, при використанні в розділі програми clauses ідентифікатора типу constants, його перша літера повинна бути рядковою для того, щоб уникнути плутанини між константами та змінними.

- У програмі може бути кілька розділів constants, однак оголошення константи повинно проводитися перед її використанням;

- Ідентифікатори констант є глобальними і можуть оголошуватися тільки один раз. Множинне оголошення одного і того ж ідентифікатора призведе до повідомлення про помилку "The declaration conflicts with another declaration of `name_of_constant`".

 

4. Розділ clauses (пропозицій)

У розділ clauses поміщаються всі факти і правила, що складають програму.

Факти - це відносини або властивості, про які відомо, що вони мають значення "істина".

Факт представляє або властивість об'єкта, або відношення між об'єктами.

Факт самодостатній. Для підтвердження факту не потрібно додаткових відомостей, і факт може бути використаний як основа для логічного висновку.

Факт в Visual Prolog складається з імені відносини і об'єкта або об'єктів, укладених в круглі дужки. Факт завершується крапкою ".".

Тобто пропозиція на природній мові Білл любить собак. (Bill likes dogs) на синтаксисі Visual Prolog буде виглядати likes (bill, dogs).

Факти крім відносин, можуть виражати і властивості. Так, наприклад, пропозиція природної мови "Kermit is green" (Керміт зелений) на Visual Prolog, висловлюючи ті ж властивості, виглядає таким чином: green (kermit).

Правила - це пов'язані відносини; вони дозволяють логічно виводити одну порцію інформації з іншої.

Правило приймає значення "істина", якщо доведено, що заданий набір умов є істинним.

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

Всі правила мають 2 частини: заголовок і тіло, розділені спеціальним знаком “ :-“.

Заголовок — це факт, який був би істинним, якщо б були істинними кілька умов. Це називається висновком або залежним ставленням.

Тіло — це ряд умов, які мають бути істинними, щоб можна було довести, що заголовок правила правдивий.

Нижче представлений узагальнений синтаксис правила в Visual Prolog:

заголовок: - < Підціль>, <Підціль>,..., < Підціль>.

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

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

Нижче представлені правила, відповідні зв'язки "любити" (likes):

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

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

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

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

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

Символ ": -" має сенс "якщо" (if). Однак if Прологу відрізняється від if, написаного в інших мовах, наприклад в Pascal, де умова, що міститься в операторі if, має бути зазначено перед тілом оператора, який може бути виконаний. Даний тип оператора відомий як умовний оператор якщо / тоді (if / then).

Наприклад, правила

означають: "Щоб довести, що Сінді любить щось, доведіть, що Білл любить це" і "Щоб довести, що Кейтлін любить щось, доведіть, що це щось зелене".

5. Розділ predicates (предикатів), class predicates

Якщо в розділі clauses програми на Visual Prolog ви описали власний предикат, то ви зобов'язані оголосити його в розділі predicates (предикатів), в іншому випадку Visual Prolog не зрозуміє, про що ви йому "говорите". У результаті оголошення предиката ви повідомляєте, до яких доменів (типам) належать аргументи цього предиката.

Visual Prolog поставляється з великим набором вбудованих предикатів (їх не потрібно оголошувати).

Предикати задають факти і правила. У розділі class predicates всі предикати перераховуються із зазначенням типів (доменів) їх аргументів.

Оголошення предиката починається з імені цього предиката, за яким йде двокрапка, відкриваюча (ліва) кругла дужка, після чого слідує нуль або більше доменів ( типів) аргументів предиката:

Після кожного домену (типу) аргументу слідує кома, а після останнього типу аргументу - закриває (права) дужка. Декларація предиката завершується крапкою. Доменами (типами) аргументів предиката можуть бути або стандартні домени, або домени оголошені вами в розділі domains.

Ім'я предиката повинно починатися з літери, за якою може розташовуватися послідовність букв, цифр і символів підкреслення. Регістр літер не має значення, однак не слід використовувати заголовні букви в якості першої літери імені предиката. Ім'я предиката може мати довжину до 250 символів.

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

Аргументи предикатів повинні належати доменам, відомим Visual Prolog. Ці домени можуть бути або стандартними доменами, або деякими з тих, що ви оголосили в розділі доменів.

Тобто якщо предикат оголошений в розділі class predicates наступним чином:

то не потрібно в розділі domains декларувати домени його аргументів, так як integer - стандартний домен. Однак, якщо цей же предикат оголосити з нестандартними доменами аргументів, наприклад:

Таким чином, при оголошенні предиката price_write1/1 вказується його тип і схема входу-виходу параметрів (flow pattern):

Оголошений тип свідчить, що аргумент Win предиката price_write1 price_write1(Win) має тип integer. Оголошена схема стверджує, що аргумент price_write1/1 зобов'язаний бути вхідним, тобто, що він є константою, а не вільною змінною. У цьому випадку предикат приймає дані через свій аргумент. Взагалі кажучи, Ви можете не вказувати всі схеми входу-виходу аргументів. Їх самостійно виведе компілятор. Якщо він не зможе це зробити, то видасть повідомлення про помилку, і Ви зможете додати необхідну схему.

Якщо передбачається, що предикат буде використовуватися тільки усередині його класу (і він не є об'єктним), він оголошується як class predicates – предикат класу. Наприклад:

6. Розділ class facts (фактів)

Однопредикатні пропозиції Хорна можуть бути оголошені як факти.

Програма на Visual Prolog являє собою набір фактів та правил. Іноді в процесі роботи програми буває необхідно модифікувати (змінити, видалити або додати) деякі з фактів, з якими вона працює. У цьому випадку факти розглядаються як динамічна або внутрішня база даних, яка при виконанні програми може змінюватися. Для оголошення фактів програми, які розглядаються як частини динамічної (або змінюється) бази даних, Visual Prolog включає спеціальний розділ — class facts. Саме в цій секції ви оголошуєте факти, що включаються в динамічну базу даних.

Наприклад:

Аргументами предиката conn/2 є пара значень типа pnt. Тип pnt визначений в класі vpiDomains. Eсть два способи, як використовувати його в класі:

- Можна зробити докладне оголошення та вказати клас, якому належить pnt:

- Або можна відкрити цей клас всередині класу:

7. Розділ domains (доменів)

Домени дозволяють задавати різні імена різним видам даних, які, в іншому випадку, будуть виглядати абсолютно однаково. У програмах Visual Prolog об'єкти у відносинах (аргументи предикатів) належать доменам, причому це можуть бути як стандартні (примітивні) (табл. 1), так і описані вами спеціальні домени.

Якщо Вам потрібні інші типи даних, окрім стандартних, необхідно визначити нові типи даних, які Ви помістите в ваш код. Такі типи даних вказуються в розділі domains.

Таблиця 1

Примітивні типи даних

integer	3, 45, 65, 34, 845, 0x0000FA1B (0x0000FA1B — це шістнадцяткове число, тобто число, виражене в системі числення з основою 16, яка використовує наступні цифри: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F)
real	3.45, 3.1416, 2.18E-18, 1.6E-19 та ін.
string	"pencil", "John Mc Knight", "Cornell University" та ін.
symbol	"Na", "Natrium", "K", "Kalium" та ін.

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

8. Розділ goal (цілі)

При запуску програми Visual Prolog автоматично виконує мету. У розділі мети (goal) пишеться

mainExe::run( main::run).

Тут ми викликаємо процедуру run(), визначення якої розміщуємо в розділі clauses..

Змінні

У Visual Prolog змінні дозволяють записувати загальні факти і правила і ставити загальні питання.

Імена змінних в Visual Prolog повинні починатися з великої літери (або з символу підкреслення), після якої може стояти будь- яку кількість букв (заголовних або рядкових), цифр або символів підкреслення. Зручно використовувати в назві змінної букви різного регістра: Income AndExpenditureAccount.

В простому запиті, щоб знайти того, хто любить теніс, можна використовувати змінні. наприклад: likes(X, tennis).

У цьому запиті буква “ X” використовується як змінна для знаходження невідомої людини.

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

likes(Person, tennis).

краще, ніж

likes (X, tennis).

тому що “ Person” має більше смислу, ніжм “ X”.

Пропозиція на англійській мові “ Bill likes the same thing as Kim”. (Білл любить те ж, що і Кім), може бути записано на Visual Prolog наступним чином:

likes (bill, Thing) :- likes ( kim,      Thing).

Thing — це змінна.

Коментарі

Гарним стилем програмування є включення в програму коментарів, що пояснюють все те, що може бути незрозуміло комусь іншому (або навіть вам, через півроку).

Багаторядкові коментарі повинні починатися з символів / * і завершуватися символами * /.

Для установки однорядкових коментарів можна використовувати або ці ж символи, або починати коментар символом відсотка “%”).

Зіставлення (matching)

У Visual Prolog є кілька прикладів зіставлення однієї речі з іншою. Ясно, що ідентичні структури співставні (порівняні) один з одним: parent (joe, tammy) порівнянно з parent (joe, tammy).

Однак зіставлення (порівняння) зазвичай використовує одну або декілька вільних змінних. Наприклад, якщо X вільна, то

parent (joe, X) порівнянно з parent (joe, tammy) і X приймає значення (зв’язується з) tammy.

Якщо ж X вже пов'язана, то вона діє так само, як звичайна константа. Таким чином, якщо X пов'язана зі значенням tammy, то parent (joe, X) сопоставимо с parent(joe, tammy), но parent (joe, X) не сопоставимо с parent (joe, millie).

Дві вільні змінні можуть зіставлятися один з одним. наприклад, parent (joe, X) сопоставляется с parent (joe, Y), зв'язуючи при цьому змінні X і Y між собою. З момента зв’язування X і Y трактуються как одна змінна, і в будь-яку зміну значення однієї з них призводить до негайної відповідної зміни іншої. У разі подібного "зв' язування" між собою декількох вільних змінних всі вони називаються сполученими вільними змінними.

У Пролозі скріплення змінних (зі значеннями) проводиться двома способами: на вході і виході. Напрямок, в якому передаються значення, вказуєте в шаблоні потоку параметрів (flow pattern). Надалі (для стислості) будемо опускати слово "шаблон" і говорити просто "потік параметрів". Коли змінна передається в пропозицію, вона вважається вхідним аргументом і позначається символом (i). Коли ж змінна повертається з пропозиції, вона є вихідним аргументом і позначається символом (о).

Оголошення режимів детермінізму

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

determ

Виконання детермінованого предиката може завершитися або невдало (fail), або успішно (succeed) і при цьому мати одне рішення.

procedure

Предикати цього виду завжди завершуються успішно і мають одне рішення. Наприклад, предикати з наступного прикладу в даній лабораторній роботі price_write2/1 і price_ write 2/1 є процедурами і можуть бути оголошені так:

multi

Такий предикат не може завершитися невдало, при цьому він має безліч рішень, наприклад:

nondeterm

Недетермінірованний предикат може завершитися або невдало, або успішно, і при цьому мати безліч рішень. Припустимо, предикати city/2 і connection/2 мають тип nondeterm і могли б мати наступне оголошення:

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

Розглянемо наступну пропозицію Хорна:

Недетермінований предикат conn(P1,P 2) повертає дві крапки, які використовує процедура drawLine(Win, P1, P 2), з'єднує ці точки прямою лінією.

Потім Пролог намагається задовольнити предикат fail, який завжди неуспішний, як і показує його ім'я. У результаті відбувається відкат, і Пролог намагається знайти інше рішення, до тих пір, поки не вичерпуються всі варіанти. Після цього він переходить до другого речення для предиката connection/1, яке завжди приводить до успіху.

Управління пошуком рішень

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

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

- предикат fail, який використовується для ініціалізації пошуку з поверненням;

- предикат cut або відсікання (позначається "!") - для заборони можливості повернення.

Використання предиката fail.

Пролог починає пошук з поверненням, коли виклик завершується невдало. Мова підтримує спеціальний предикат fail, викликає неуспішне завершення, і ініціалізує повернення. Дія предиката fail рівносильно ефекту від порівняння 2= 3 або інший неможливою підцілі. Наступний приклад ілюструє використання цього спеціального предиката.

 

Приклад 1 – Використання предиката fail

Дана програма ставить у відповідність імені батька ім'я його дитини.

Лістинг програми

Предикат everybody в програмі використовує fail для підтримки пошуку з поверненням. Задача everybody – знайти всі рішення для father і видати повну відповідь. Предикат everybody виводить на екран

leonard is katherine’s father.

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

Результат виконання програми наведений на рис. 1.

Рис. 1 Результат виконання програми із прикладу 1

 

Приклад 2 – Прайс-лист

Представлений лістинг являє собою закінчену програму на Visual Prolog, що є невеликим прайс-листом продуктового магазину. Так як використовуються тільки стандартні домени, розділ domains в цій програмі не потрібен.

Лістинг програми

Запустимо цю програму, в результаті чого на консоль буде виведений весь прайс-лист. У відповідь на пропозицію ввести ціну введемо, наприклад, 20000. На консоль буде виведено

meat 20000

і з'явиться запит ввести продукт. Так як тип необхідного значення строковий, то вводимо рядок у "", інакше відбудеться помилка.

Якщо введемо "bread", отримаємо

bread 1200

bread 1380

Результат роботи програми наведений на рис. 2.

Рис. 2. Результат виконання програми з прикладу 2

Завдання

За допомогою отриманих в даній лабораторній роботі знань написати програму на мові Пролог наступних типів:

1) Телефонний довідник.

2) Адресну книжку.

3) Каталог автомобілів.

Контрольні питання

1. З яких розділів зазвичай складається програма на Visual Prolog 7. x?

2. Дайте визначення понять факт, правило, заголовок?

3. Назвіть правила іменування предикатів.

4. Перерахуйте основні домени в Visual Prolog.

5. Перерахуйте обмеження, що накладаються на використання констант.

6. Наведіть приклад зіставлення однієї речі з іншою.

7. У якому випадку змінні називаються сполученими вільними змінними.

Зміст звіту:

- титульний аркуш;

- мета роботи;

- основні розділи програми на мові Visual Prolog;

- лістинг програми;

- результат виконання.