Загальний огляд мови Пролог
Перші повідомлення про Пролог з`явились на початку сімдесятих років. Він належить до класу логічних мов програмування. Основні ідеї розробки яких запропонували Р.Ковальськи і П.Хейс. Перший інтерпретатор Пролога був розроблений французами в Марселі під керівництвом А.Колмерое в 1973 році. Наступна версія, виконана Д.Уореном - Единбугська реалізація Пролога на машині DEC-10, перетворила Пролог і разом з ним логічне програмування із площини теоретичних досліджень в площину практичного програмування, зробила його корисним інструментом для вирішення різних задач штучного інтелекту. Про великі можливості мови Пролог свідчить і той факт, що японські вчені вибрали його в якості базової мови для створення обчислювальних систем п`ятого покоління.
Для Прологу характерним є і той факт, що програміст повинен мислити в термінах цілей. Що ми під цим будемо розуміти? Коли ми програмуємо, застосовуючи мову програмування низького рівня, тоді ми повинні описувати як дещо треба зробити ЕОМ. Коли ж використовується мова програмування високого рівня, тоді необхідно вказати що ж потрібно зробити. На відміну від традиційних мов програмування, Пролог вимагає від програміста змінити форму мислення по написанню програм. Прологівська програма являє собою набір визначень ситуацій і формулювань задач, замість того, щоб детально описувати варіанти рішень цих задач. Основою Пролога є обмежений, але на диво потужний і гнучкий набір програмних механізмів, який включає в себе: співставлення зразків, задання структур даних типу дерева і автоматичне повернення. Назва Пролог утворилась як скорочення від “програмування в термінах логіки” і його можна віднести до мов програмування, які будуються на описовому або ж декларативному підході до програмування.
Можна виділити два рівня характеристики прологівської програми: декларативний і процедурний. Перший з них визначає за допомогою відношень, яким повинен бути результат роботи програми. Другий - як цей результат був отриманий і які з відношень реально оброблялись. Пролог-системи значну частину процедурних деталей виконують самостійно без втручання програміста. Останній, таким чином, може більш уваги приділяти легшому декларативному аспекту програми не відволікаючись на організацію процеса обчислень, якщо його не хвилює питання ефективності обчислень.
Попередньо Пролог відносився до теоретичних мов програмування і в більшості використовувався як інструментарій в наукових дослідженнях. На це впливало і те, що довгий час вчені із США не сприймали його переваг для вирішення задач штучного інтелекту. Джон Малпас пояснює цей факт тим, що по перше серед вчених США були сильними лісповські традиції (мова ЛІСП створена в Массачусетському технологічному інституті) і по друге - попереднє знайомство з мовою логічного типу Мікропленнером було невдалим. Остання була реалізована дуже не ефективно. Та з створенням швидких інтерпретаторів і компіляторів Пролог зайняв почесне місце не тільки серед найбільш використовуваних мов вирішення задач штучного інтелекту, а й серед мов, які використовуються спеціалістами в галузях реляційних баз даних, програмної інженерії, задання знань, експертних системах і багатьох інших.
1.2.Переваги і недоліки мови Пролог.
Резюмуючи сказане раніше можна виділити наступні переваги Прологу:
1.Пролог має чітку математичну основу, дуже близьку до людського мислення.
2.Використання єдиної мови специфікацій (числення предикатів) для опису вимог до програм і опису самої програми на Пролозі дозволяє поєднувати процес написання програми і її верифікацією.
3.Застосування відношення, як базового поняття мови, надає змогу зручно працювати з реляційними базами даних.
4.Паралельний принцип організації обчислень дозволяє просто і природньо реалізовувати Пролог-програму на паралельному комплексі.
5.Пролог підтримує обчислення, які базуються на пошуку через зворотній ланцюжок міркувань. Це забеспечує ефективність використання Прологу при побудові експертних систем.
6.Пролог може зберігати за допомогою “логічних змінних” проміжні результати обчислень для наступного використання. Це дозволяє природньо вирішувати проблему організації логічного виведення.
Поряд з вказаними перевагами спеціалісти зазначають наступні вади Прологу.
1.Складність розуміння процесу виконання програми на Пролозі, пов`язані з “невидимим” порядком побудови виведення результату програмою.
2.Погані засоби для вияву екстралогічних властивостей (оператори динамічного приєднання і видалення тверджень).
3.Відсутність досконалих засобів для розробки і відлагодження великих програм.
4.Недостатні засоби підтримки модульного принципу програмування.
1.3.Числення предикатів - математична основа мови.
В основі Прологу лежить поняття відношення, яке взяте з предикатних логік. Слово “предикат” відноситься до розділу математичної логіки, в якому досліджуються операції над логічними висловленнями. В логіці предикатів під предикатом розуміється деяка властивість, логічна функція від довільного числа аргументів, яка приймає тільки два значення - “істина” або ж “хибність”.
Логіку предикатів, в деякій мірі, можна вважати спеціальним математичним апаратом формалізації людського мислення. Звідки, мови програмування логічного типу є найбільш зручними, для роботи з базами знань.
Числення предикатів використовує наступні основні елементи:
1)константні терми с1,с2,...;
2)змінні терми х1,х2,...;
3)функціональні терми f1,f2,...;
4)предикатні букви p1,p2,...;
5)логічні символи ¾>,&,È,~,",$;
6)спеціальне висловлення .
Елементарне висловлення складається з предикату і зв`язаних з ним термів. Складні висловлення будуються з елементарних за допомогою логічних зв`язок. Серед них можна виділити логічні зв`язки: “і” (and, &), “або ж” (or,È) , “ні” (not, ~) і імплікація (¾>). Імплікація займає особливе місце, оскільки вона використовується для побудови специфічних правил і читається “якщо..., тоді...”.
Для того щоб в численні предикатів можна було використовувати змінні терми, застосовується спеціальна структура - квантор.
Квантори використовуються для зазначення міри, в якій значення змінних повинні бути істинними для того, щоб в цілому висловлення стало істинним. Виділяють квантор узагальнення (") і квантор існування ($).
В логіці предикатів елементарним об`єктом, який має значення “істина”, є атомарна формула. Атомарна формула включає в себе символьні позначення предикату і термів, які відіграють роль аргументів цього предикату. В загальному випадку позначення предикату є ім`ям відношення, яке існує між аргументами.
Атомарна формула записується як позначення предикату і має наступний вигляд: Р(t1,t2,...,tn), де Р - позначення предикату, а t1,t2,...,tn - терми.
Число термів для кожного предикату фіксоване і називається його арністю. Терми визначаються наступним чином:
1)константний терм - терм;
2)змінний терм - терм;
3)якщо арність функціональної букви є n, а t1,t2,...,tn - терми, тоді f(t1,t2,...,tn) також терм.
Правильно побудована формула (ППФ) отримується в результаті комбінування атомарних формул за допомогою логічних зв`язок.
Символ •позначає хибну замкнуту формулу і визначає поняття “протиріччя”. Так формула А ¾> ” означає хибність А, вона еквівалентна формулі ~А.
Серед формул можна виділити спеціальний клас формул - тотожньо істинні формули, які називають аксіомами. Приклад аксіоми:
~ ~ А <¾ ¾> А.
Більш детальний опис маніпулювання з формулами і правилами виведення можна знайти в довільному підручнику по математичній логіці.
1.4.Побудова теорії деякої області знань.
Побудова теорії деякої області знань включає в себе аналіз структури цієї області і вибір позначень, які визначають особливості даної структури. Потім будуються ППФ, які описують цю структуру. Множина ППФ є теорією цієї області знань, в якій кожна ППФ - аксіома.
Аналіз області знань включає виділення вагомих суттєвостей із цієї області. Дану множину називають областю інтерпретації. Далі визначаються найбільш важливі функції над елементами області інтерпретації, якщо такі існують, і значимі відношення між елементами області інтерпретації. По закінченню значимі відношення оформлюються синтаксично в вигляді аксіом.
Під функцією будемо розуміти відображення n елементів із області інтерпретації (де n - арність функції) на один з елементів цієї області.
Нехай областю є службові відношення між людьми в деякій фірмі. Областю інтерпретації буде наступна множина людей:
(Іван; Ігор, підлеглий Івана; Петро, підлеглий Івана; Микола, друг Петра).
На цій області можна виділити унарну функцію “друг”. Наприклад, друг (Петра) ¾> Микола.
Відношенням називають відображення n елементів із області інтерпретування на елемент множини (істина, хибність). В нашому прикладі можна виділити бінарне відношення “підлеглий”. Так, підлеглий (Івана, Ігор) матиме значення “істина”, а підлеглий (Ігор, Микола) прийме значення “хибність”.
Якщо в деякому конкретному випадку аргументів відношення буде істинним, тоді кажуть що відношення справджується.
Після фіксації області інтерпретування переходять до вибору позначень елементів області: констант, функцій, відношень. Відмітимо, що функція сама по собі не може мати значення - його може мати тільки конкретне використання функції. Аналогічне можна сказати і про відношення.
Проілюструємо це на нашому прикладі.
Спочатку виберемо позначення для констант і припишемо їм значення, які відповідають елементам області інтерпретації.
Значенням a буде Іван.
Значенням b буде підлеглий Івана Ігор.
Значенням с буде підлеглий Івана Петро.
Функцію “друг” позначимо f, тоді семантика цієї функції визначиться:
Значенням f(c) буде Микола.
Якщо позначимо через Р введене нами відношення “підлеглий”, тоді його семантика виразиться:
Значенням P(a,b) буде істина.
Значенням P(b,a) буде істина.
Значенням P(c,a) буде істина.
Значенням P(a,c) буде істина.
Значенням P(b,c) буде хибність.
Значенням P(c,b) буде хибність.
Значенням P(b,f(c)) буде хибність.
Значенням P(f(c),b) буде хибність.
Значенням P(a,f(c)) буде хибність.
Значенням P(f(c),a) буде хибність.
Значенням P(c,f(c)) буде хибність.
Значенням P(f(c),c) буде хибність.
Із даних атомарних формул маємо можливість будувати ППФ.
Інтерпретація, яка робить ППФ істиною називається моделлю цієї ППФ. Аналогічно визначається і модель теорії. Про ППФ, або ж теорію, яка приймає значення істина хоча б на одній інтерпретації, кажуть, що вона задовільна. Якщо ППФ, або ж теорія є хибною на всіх інтерпретаціях, тоді її називають незадовільною або ж непослідовною.
1.5.Від формальної логіки до логічного програмування.
В логіці предикатів існують методи доведення того, буде чи ні конкретна ППФ наслідком деякої теорії. Природньо виникає бажання автоматизувати таке доведення за допомогою предикату. В більшості підходів до цієї проблеми використовується процедура спростування. Розглянемо основні ідеї цієї процедури.
лддІз визначення тотожньої істинності і непослідовності можна зробити висновок, що ППФ буде тотожньо істинною тоді і тільки тоді, коли прибавлення в теорію заперечення даної ППФ перетворить цю теорію в непослідовну.
Теорія буде непослідовною, якщо в ній можливо вивести протиріччя наступного вигляду
А & ~ А.
Для вирішення згаданих задач дуже зручною є фразова форма логіки. Фразова форма логіки предикатів задає такий спосіб запису формул, який використовує тільки з`єднувачі типу &, È і ~.
Негативна або ж позитивна атомарна формула називається літералом. Кожна формула - множина літералів, які з`єднані символом È. Негативні і позитивні літерали відповідно групуються. Схематично фраза має наступний вигляд:
Р1 È Р2 È ... Рn È N1 È N2 È ... Nn, де P1 ... Pn - позитивні літерали, а N1... Nn - негативні. З другої сторони фразу можна розглядати як узагальнення поняття імплікації. Дійсно, якщо А і В атомарні формули, тоді формулу А ¾>В можна переписати і в такому еквівалентному вигляді: ~ А È В. Звідки отримаємо фразову формулу В È ~ А.
Фраза має наступну семантику. Всі позитивні атомарні формули виступають в ролі альтернативних заключень, а негативні - є необхідними умовами. Наприклад, А È В È ~С È ~D зазначає що А і В будуть істиними тоді і тільки тоді, коли є істиними С і D.
Елементарна фраза має тільки один літерал. Теорія записується в вигляді множини фраз, які неявно з`єднані між собою символом &. В літературі зустрічається і друга форма запису фрази за допомогою зворотньої стрілки, яка читається як “імплікується”. Так остання фраза може мати вигляд А, В <¾ ~С, ~D.
Для скорочення об`ємів обчислень на практиці використовують спеціальний клас фраз, який дістав назву фраз Хорна. Фраза Хорна - це фраза, яка має тільки один позитивний літерал. Одну фразу Хорна можна записати декількома способами. Наприклад, А È ~В È ~С È ~D еквівалентне А <¾ В, С, D і в системі Турбо-Пролог буде мати вигляд А: ~В, С, D.
Для любої системи логічного програмування характерною є та обставина, що для виконання програми (побудови виведення результату) використовується вмонтована система автоматичного пошуку. Механізм пошуку логічного висновку Прологу бере свій початок від методу резолюцій Робінсона.
Правило резолюції виведення логічного висновку працює наступним чином. Дві фрази можуть резольвувати між собою, якщо одна з них має позитивний, а друга - негативний літерал з одним і тим же позначенням предикату, та однаковою кількістю аргументів, і якщо аргументи обох літералів можуть бути уніфіковані (погоджені). Наприклад, фраза P(a,b) È ~Q(c,d) і фраза Q(c,d) È R(b,c) дають резольвенту P(a,b) È R(b,c). Якщо ж аргументом відношення є змінна, то вона уніфікується з константою, а резольвента буде мати дану константу на місцях попереднього розташування змінної.
Розглянемо дві фрази спеціального вигляду:
Р(а) - заключення без умови і ~Р(а) - умова без заключення. Наявність цих двох фраз в одній теорії є протиріччям. Якщо вони резольвуються між собою, тоді отримана резольвента називається пустою фразою.
Якщо при резолюції двох фраз, що входять в склад теорії, отримується пуста фраза, тоді теорія буде непослідовною.
Розглянемо на прикладі застосування принципу резолюції і уніфікації.
Нехай маємо відношення АРТИСТ(х), яке позначає твердження х є артистом і аналогічне відношення СПІВАК(х). Це дає змогу вираз “співак є артистом” формалізовати наступною імплікацією:
СПІВАК(х) ¾> АРТИСТ(х).
Тепер, після задання виразу “Яремчук - співак”, попробуємо довести за допомогою методу резолюції вираз “Яремчук - артист”.
Спочатку, добавимо до попередніх фраз теорії формулу заперечення того твердження, яке ми хочемо довести. Матимемо наступні фрази теорії:
СПІВАК(х) ¾> АРТИСТ(х) (1)
СПІВАК(Яремчук) (2)
~АРТИСТ(Яремчук) (3)
Формулу (1) перепишемо в вигляді ~СПІВАК(х) È АРТИСТ(х). Потім зробимо уніфікаційну підстановку х: Яремчук відносно формул (1) і (2). В результаті можемо видалити тотожньо істинну формулу:
~СПІВАК(Яремчук) È СПІВАК(Яремчук).
Залишок з`єднаємо зв`язкою È і знову ж видалимо. В результаті маємо пусту фразу, що дає непослідовність нашої теорії. Звідки, методом обгрунтування логічного висловлення виводиться формула АРТИСТ(Яремчук). Наш приклад в синтаксисі системи Турбо-Прологу буде мати вигляд:
АРТИСТ(х): - СПІВАК(х).
СПІВАК(Яремчук).
? - АРТИСТ(Яремчук).
1.6.Механізм логічного виведення і керування пошуком.
Найчастіше , програма на Пролозі є послідовністю процедур, кожна з яких реалізує конкретний предикат. Процедура будується із речень, які мають форму:
А: -В1, В2,..., Вn.
Наше речення інтерпретується наступним чином: “А є істинним, якщо В1,В2,...,Вn є істинними”.
Кажуть, щоА є заголовком цього речення, а В1,В2,...,Вn його тіло. Якщо n=0, тоді таке речення визначає деякий факт і записується “А”.
Речення А і Ві є прикладами цілей або ж викликами процедур, які складаються із предикату і його аргументів R(x,y).
Якщо отримано запит (іншими словами ціль, яку необхідно задовільнити), Пролог пробує визначити його істинність двома способами. По перше, тому що факти завжди є істинними, тоді ціль успішно задовільняється, якщо вона співставляється з існуючим фактом. По друге, ціль вважається істинною, якщо вона співпадає з деяким заголовком “А” всі підцілі якого “В1,В2,...,Вn” можуть бути успішно завершені. Якщо спроба співставлення підцілей і фактів закінчується невдало, а залишаються альтернативні і ще не використані правила та факти, тоді Пролог-система буде здійснювати повернення і використовувати ці альтернативи. Якщо всі альтернативи перебрані і закінчились невдало, тоді кажуть що початкова ціль незадовільна.
Порядок оцінки цілей в самому реченні - зліва направо.