мова логічного програмування Прологмова логічного програмування Пролог мова логічного програмування Пролог Зміст 1.ПРОЛОГ - МОВА ЛОГІЧНОГО ПРОГРАМУВАННЯ. 2.ОСНОВНІ КОНЦЕПЦІЇ ПРОЛОГУ. 3.СТРУКТУРА ПРОГРАМИ PDC ПРОЛОГУ. 4.КОНТРОЛЬ ПОШУКУ РІШЕНЬ. 5.ПРОСТІ ТА СКЛАДНІ ОБ.ЄКТИ. 6. ІТЕРАЦІЯ І РЕКУРСІЯ. 7. РЕКУРСИВНІ СТРУКТУРИ ДАНИХ. 8. РОБОТА З СПИСКАМИ В ПРОЛОЗІ. 9. ТЕХНІКА ПРОГРАМУВАННЯ В ПРОЛОЗІ. 10.ОСОБЛИВІ ТЕХНІЧНІ ПРИЙОМИ ДЛЯ ПРОФЕСІОНАЛІВ. 1.ПРОЛОГ - МОВА ЛОГІЧНОГО ПРОГРАМУВАННЯ. 1.1.Загальний огляд мови Пролог. Перші повідомлення про Пролог з.явились на початку сімдесятих років. Він належить до класу логічних мов програмування. Основні ідеї розробки яких запропонували Р.Ковальськи і П.Хейс. Перший інтерпретатор Пролога був розроблений французами в Марселі під керівництвом А.Колмерое в 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» можуть бути успішно завершені. Якщо спроба співставлення підцілей і фактів закінчується невдало, а залишаються альтернативні і ще не використані правила та факти, тоді Пролог-система буде здійснювати повернення і використовувати ці альтернативи. Якщо всі альтернативи перебрані і закінчились невдало, тоді кажуть що початкова ціль незадовільна. Порядок оцінки цілей в самому реченні - зліва направо. Вправи. 1.1.Базуючись на принципі силлогізму, довести: а)Якщо задані дві посилки: Всі українці люблять пісні. Всі кияни - українці. Тоді буде коректним висловлення: Всі кияни люблять пісні. б)Якщо задані дві посилки: Всі програмісти люблять жувальну гумку. Деякі програмісти живуть в Києві. Тоді буде коректним висловлення: Деякі люди з Києва люблять жувальну гумку. 1.2.За область знань візьмемо арифметику, а областю інтерпретації будуть натуральні числа. Область інтерпретації в цьому випадку нескінченна. Побудуйте теорію цієї області, розробивши задання довільного числа в вигляді терму. 1.3.Маємо наступну множину фраз Р(а) ( ( Q(a,b) Q(x,y) ( ( R(x,y) S(b) R(a,b) Потрібно вияснити, чи є фраза Р(а), наслідком існуючої множини фраз. 2.ОСНОВНІ КОНЦЕПЦІЇ ПРОЛОГУ. 2.1.Факти та правила. При побудові речень Прологу використовується той же підхід що й в предикатних логіках. Спочатку відкидаємо всі несуттєві слова. Потім трасформуємо речення, виставляючи на перше місце відношення. Наприклад, наступні речення трансформуються в синтаксис предикатної логіки: Китайська авторучка зручна. зручна(китайська_авторучка). Вані подобається авторучка, якщо вона зручна. подобатись(ваня,авторучка) if зручна(китайська_авторучка). Програміст визначає об.єкти і відношення. Потім формулює правила про те, коли ці відношення справджуються. Наприклад, речення: Ваня любить автомобілі ілюструє відношення між об.єктами Ваня і автомобілі. зв.язком є любить. Правило, яке визначає, коли речення: Ваня любить автомобілі буде істинним, має вигляд: Ваня любить автомобілі, якщо вони швидкі. Факти. В Пролозі зв.язок між об.єктами називається фактом. Факти можуть виражати як властивості, так і відношення. Так речення: Прапор червоний. Валя - студентка. можуть бути задані наступними фактами: червоний(прапор) студентка(Валя). Правила визначають, які висновки можна зробити із даних фактів. Запити. Враховуючи, що Пролог складається з множини фактів, ми можемо задавати йому питання про ці відношення у вигляді запитів. Пролог будує відповідь і виводить її до друку. Наприклад, речення Що любить Ваня може бути трасформоване в запит любить(ваня, Що). Важливо відмітити, що перший аргумент запиту починається з маленької букви (константа), а другий аргумент починається з великої букви (Що виступає в ролі змінної). Змінні Прологу дозволяють вам записувати загальні факти і правила, а також задавати загальні питання. Узагальнення. 1.Програма на Пролозі будується із двох типів фраз (речень): фактів і правил. Факти - це відношення, або ж властивості, про які ви, програміст, знаєте, що вони істинні. Правила - це залежні відношення. вони дозволяють Прологу робити виведення, порівнюючи одну частину інформації з іншою. 2.Правила Прологу складаються з трьох частин: голови, символу, тіла. Голова - це факт, який буде вірним, якщо деяка кількість умов виконається. Голову ще іноді називають заключенням, або ж відношенням залежності. Символ - відділяє голову правила від тіла. може бути текстовим типу or або ж if. Тіло - це множина умов (або список файлів), котрі повинні бути істинними, для того щоб Пролог міг довести, що голова правила вірна. Розглянемо наступну програму: 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). 2.2.Як змінні отримують свої значення. Як ви вже мабуть відмітили, в Пролозі не має операції присвоєння. Змінні Прологу отримують свої значення, порівнюючи їх з константами в фактах і правилах. Поки змінна не отримає свого значення, вона називається вільною, а коли отримує значення - зв.язаною. Але вона залишається зв.язаною тільки на час, який необхідний для отримання одного розв.зку на запит, потім Пролог звільнює її, повертає і шукає альтернативні розв. язки. Розглянемо наступну програму: 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 - вільна . її значення невідомо до тих пір, поки ПРОЛОГ пробує знайти розв.язок, інший аргумет - reading - відомий . ПРОЛОГ робить пошук факту, який порівнює першу частину запиту. Використовуючи перший факт програми: likes(ellen,reading) Враховуючи другу частину запиту, Пролог повинен шукати факт: likes(ellen,swimming) ПРОЛОГ веде пошук цього факту з самого початку программи, але співставлення не проходить (тому, що не існує такого факту в програмі). ПРОЛОГ зразу |розв.язує| Person і пробує знайти інший розв.язок першої частини запиту з Person як з вільною змінною. Пошук іншого факту, який задовільняє першу частину запиту, починається з місця відміченого вказівником. Вказівник ставиться для реалізації перебору з повертаннями. Пролог шукає іншу особу, яка любить читати і знаходить факт likes (eric, reading). Тому Person зв.язується з eric. Він задовільняє і другій частині запиту. Пролог відповідає: Person = eric 1 Solution 2.3.Анонімні змінні. Анонімні змінні використовуються у випадку, коли вам потрібна часткова інформація із запиту. За допомогою анонімних змінних ігноруються значення, які вам не потрібні. Наступний приклад демонструє використання анонімних змінних. predicates male(symbol) female(symbol) parent(symbol, symbol) clauses male(bill). male(joe). female(sue). female(tammy). parent(bill, joe). parent(sue, joe). parent(joe, tammy). Анонімна змінна може бути використана на місці любої змінної. Відмінність полягає в тому, що анонімна змінна ніколи не отримає значення. Наприклад, якщо вам потрібна інформація тільки про батьків, тоді ви можете використати запит: Goal:parent(Who, _) де символ _ позначає анонімну змінну. Система видасть результат: Who=bill Who=sue Who=joe 3 Solution. Анонімні змінні можуть також використовуватись і в фактах: owns(_,shoes). eats(_). В цьому випадку анонімна змінна зрівнює все. 2.4.Складні цілі: кон.юнкція та диз.юнкція. Ви можете використати складну ціль, щоб знайти рішення, в якому дві підцілі А і В справджуються (кон.юнкція), або розв.язок, в якому справджується хоча б одна із підцілей А або В (диз.юнкція). Наприклад, розглянемо програму: predicates car(symbol,real,integer,symbol,integer) truck(symbol,real,integer,symbol,integer) clauses car(chrysler, 130000, 3, red, 12000). car(ford, 90000, 4, gray, 25000). car(datsun, 8000, 1, red, 30000). truck(ford, 80000, 6, blue, 8000). truck(datsun, 50000, 5, orange, 20000). Загрузимо і запустимо цю програму, задавши ціль: Goal: car(Make,Odometer,Years_on_road,Body,25000). пробуємо знайти автомобіль, вартість якого становить рівно 25000. Пролог-система видасть одне рішення - ford. Але такий запит не природній. В житті ми будуємо питання іншим чином. Чи існує в продажі автомобіль, вартість якого менша за 25000? Таке питання можна реалізувати наступним складним запитом: car(Make,Odometer,Years_on_road,Body,Cost) and Cost < 25000. Якщо ж ми хочемо реалізувати в Пролозі питання наступного типу: чи існує в продажі автомобіль або вантажівка, вартість яких менша 25000? Тоді ми повинні використовувати складну ціль: car(Make,Odometer,Years_on_road,Body,Cost) and Cost < 25000 or truch(Make,Odometer,Years_on_road,Body,Cost) and Cost < 25000. Узагальнення. 1.Програма Прологу складається із фраз. Фрази бувають двох типів: факти та правила. * Факти - це відношення або властивість, про вірність яких програміст попередньо знає. * Правила - це залежні відношення. Вони дозволяють Прологу отримувати деяку інформацію із іншої. 2.Факти мають загальну форму: property(obj, obj1, ... objn) або ж relation(obj, obj1, ... objn) , де property виражає властивість об.єктів, а relation - відношення між об.єктами. 3.Кожний факт відноситься до одного або ж декількох об.єктів. Наприклад, в факті Прологу likes(tom,baseball) відношенням є likes, а об.єктами tom і baseball. Він описує речення: Тому подобається бейсбол. А в факті left-hander(tom) властивістю є left-hander, об.єктом - tom. Він описує речення : Том - лівша. 4.Правила мають загальну форму: голова if тіло, яка в програмі приймає вигляд: relation(obj, obj1, ... objn) if relation(obj, obj1, ... objn) and .... relation(obj, obj1, ... objn). 5.При виборі імен змінних і констант, ви повинні дотримуватись наступних обмежень: * Імена змінних повинні починатись із великої букви. За нею може зустрічатись довільне число символів. символами є букви, цифри та символ підкреслення. 6.Предикат - це символьне ім.я (ідентифікатор), яке пов.язує відношення з його аргументами. Програма - це послідовність фраз і директив, а процедура - це послідовність фраз, які визначають предикат фрази. 7.Змінні дозволяють вам записувати загальні факти та правила, а також задавати загальні питання. * Змінні в Пролозі отримують свої значення при співставленні з константами в фактах і правилах. * Тому, що змінна є зв.язаною тільки в середині однієї фрази, не можна зберігати інформацію, присвоївши значення змінній. 8.Анонімна змінна ніколи не отримує значення. 9.Коментарі використовуються традиційним для програмістів чином. Коментар починається символами /* і закінчується символами */ . 2.5.Способи Співставлення. В Пролозі існує декілька способів співставлення: 1. Ідентичні структури співставляються між собою. 2. Вільна змінна співставляє константу або раніше прив.язану змінну і стає зв.язаною з цією величиною. 3. Дві вільні змінні можуть співставляться і бути зв.язаними між собою. На протязі часу зв.зування, вони розуміються як одна змінна. Іншими словами, якщо одна із змінних отримала якесь значення, інша - зразу ж отримує те ж значення. Наприклад, відношення parent(joe,X) співставляючись з Parent(joe,Y) ... зв.язує змінні Х та У відповідним чином. 4. В Пролозі зв.язування (присвоєння) проходить двома способами: на вході і виході. Коли змінна потрапляє в фразу, вона стає вхідним параметром і позначається (i). а, коли виходить із фрази - стає вихідним параметром, який позначається (о). Позначення. Для полегшення читання в Пролозі використовуються наступні позначення: :- cимвол if. , слово аnd. . cлово or . Вправи. 2.1.Напишіть речення українською, які говорять про те, що визначають для людини наступні фрагменти Прологу: 1.дівчина (Галя). 2.подобається (Що, івану). 3.подобається (Що, івану) if подобається (Що, петру). 2.2.Напишіть фрагменти прологівських програм, які задають наступні твердження української мови: 1.Місто - Київ. 2.Місто Київ красиве. 3.Київ - столиця України. 4.Як називається столиця України? 2.3.Напишіть правило Прологу, яке відображає наступну ситуацію. Ми маємо факти батько(микола, іван), мати(ніна, іван). Потрібно описати правило, яке визначає батьків Івана. 2.4.Нехай у Пролог системи є набір фактів: батьки(микола, ніна, іван) батьки(петро, галя, андрій) батьки(віктор, надія, марія). Кожний з фактів трактується так. Перші два аргументи предикату є батьками особи, яку визначає третій предикат. Що буде реалізовувати запит: 1.Goal: батьки(X,Y,_). 2.Goal: батьки(_,_,Х). 3.СТРУКТУРА ПРОГРАМИ PDC ПРОЛОГУ. 3.1.Основні розділи програми. В якості реалізуючої системи Прологу будемо розглядати PDC Пролог. Він вибраний тому, що на противагу більшості реалізацій Прологу, є компілятором. В загальному, програма PDC Прологу (надалі будемо писати просто Пролог) складається з 3-4 розділів. Розділ clauses - головна частина програми Прологу. Тут записуються факти та правила, які будуть використані для задовільнення цілі програми. Розділ predicates - використовується для об.яви предикатів та доменів і опису типів їх аргументів. Коли ви об.являєте предикат, ви вказуєте Прологу які домени аргументів належать даному предикату. В ньому повинні бути присутніми всі предикати, зазначені в розділі clauses. При використанні вмонтованих предикатів, наприклад, таких, як write, makewindow, nl і т.д., об.являти їх не має потреби. Опис предикату починається з імені, потім, якщо вони існують, іде список типів аргументів, розділених комами і взятими в круглі дужки. Типи аргументу є або ж стандартними доменами, або ж доменами, які ви об.явили в розділі domains. Ім.я предикату повинно бути ідентифікатором. Розділ domains - використовується подібно конструктору типів type в Паскалі. За допомогою цього розділу можна перейменувати /перевизначити/ стандартні домени і описати домени складних типів даних. Якщо в вашій програмі використовуються тільки стандартні домени, тоді в розділі domains взагалі не має потреби. Розділ goal - використовується для задання вмонтованих (внутрішніх) цілей, коли ви бажаєте, щоб програма працювала незалежно від розвитку середовища Прологу. Іншими словами, якщо ви плануєте компілювати програму в самостійно виконувану програму, ви можете явно вказати ціль виконання. Розділ constants - застосовується для об.яви констант. Використовується синтаксис: <�Ідентифікатор> = <�Макровизначення>. Тут присутні наступні обмеження: в одній стрічці повинно бути визначення тільки одної константи. заборонена рекурсія при визначенні константи. в описі констант система не розпізнає великі та малі літери. ідентифікатори констант є глобальними і можуть бути об.явлені тільки один раз. Розділ database це розділ бази даних. Іноді під час виконання програми вам необхідно змінити деякі факти, з якими працює програма. Факти знаходяться в динамічній або внутрішній базі даних. Факти, котрі розміщуються в динамічній базі даних, повинні бути описані в розділі database. 3.2 Стандартні домени. Пролог має декілька вмонтованих стандартних доменів, основні з яких приводяться нижче. Ви можете використовувати стандартні домени при опису типів аргументів предикату. Їх не потрібно визначати в розділі domains. Домен Опис char integer real символ, взятий в одинарні лапки цілі від -32768 до 32767 числа, з необов.язковим знаком + або - , який стоїть перед деяким числом DDDDDDD, потім необов.язкова десяткова крапка (.), яка стоїть перед наступним числом DDDDDDD і необов.якова експоненційна частина (е(+ ( -)DDD):<+: ->DDDDD<.>DDDDDDDDDD> Приклади дійсних чисел: 42705 9999 86.74 9111.769483 521е238 67.85е+21 Допустимий діапазон чисел від 1е-307 до 1е+308. При необхідності цілі числа автоматично перетворюються в дійсні. string довільна послідовність символів, які заключені в подвійні лапки. symbol Існує два формати символів: 1. послідовність букв, чисел і підкреслень, які починаються з великої букви. 2. послідовність символів, які заключені в подвійні лапки (випадок, коли символ не починається з великої букви або ж коли містяться проміжки). Число аргументів предикату називається арністю предикату. Пролог допускає предикати з однаковою назвою але різною арністю. Пролог проводить автоматичне перетворення доменів: 1. між стрічками і символами. 2. між цілим, символьним і дійсним доменом. 3.3.Синтаксис правила. Як ми вже зазначали, синтаксис правила складається з трьох частин: голова: - <�підціль>, <�підціль>, ... , <�підціль>. Кожна підціль викликає відповідний предикат Прологу. Пролог - система тестує викликаний предикат і перевіряє чи може він задовільнитися. Якщо поточна підціль буде задоволена, тоді виклик справджується і обробка переходить до наступної підцілі. Якщо обробка успішно досягла крапки, тоді кажуть, що правило істинне. Якщо якась з підцілей завершується невдачею, тоді Пролог - система повертається назад і переглядає альтернативи попередньо переглянутих підцілей, але з уже іншими значеннями параметрів. Цей процес називається бектрекінгом. 3.4.Директиви комп.ютеру. Ви можете включити в програму деякі директиви комп.ютеру безпосередньо в програмі або ж вибравши пункт меню Options /Compiler Directives. Наприклад, директиву include. За допомогою директиви include ви можете підключити до програми написані вами попередньо процедури. Це робиться наступним чином. Додамо стрічку include «my.pro» на початок вашої програми. А в файлі my.pro описуються процедури, які використовуються в вашій програмі. 3.5.Бектрекінг. Часто при вирішенні конкретних задач вам необхідно переглядати всі можливі шляхи розв.язку задачі. Якщо розглянутий шлях не дає відповіді, ви мусите переглянути альтернативний шлях. Такий підхід до розв.язку задач дістав назву бектрекінг. Пролог реалізує бектрекінг таким чином. На початку пошуку вирішення поставленої проблеми, він розміщує маркер на місце проглядання і вибирає першу підціль. Якщо її вирішення закінчиться невдачею, тоді Пролог повертається в точку, відмічену маркером і пробує знайти альтернативну підціль. При поверненні в точку бектрекінгу, він звільня всі змінні, зв.язані після входу в дану точку. Розглянемо наступну програму. 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. Тому Пролог пробує підібрати наступний пункт. Подальший пошук визначається третім правилом бектрекінгу. Коли підціль відповідає голові, тоді наступним повинно задовільнятися тіло даного правила. Тіло правила в свою чергу створює нові підцілі, котрі повинні бути задоволені. І накінець, четвертий принцип бектрекінгу говорить. Ціль буде задоволена, коли будуть знайдені відповідні факти для кожного рівня дерева цілі. 3.5.1.Бектрекінг з внутрішньою ціллю. Бектерінг з внутрішньою ціллю ілюструється програмою: predicates type(symbol, symbol) is_a(symbol, symbol) lives(symbol, symbol) can_swim(symbol) goal can_swim(What) , write(|A |, What, | can swim.|). 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). Вправи. 3.1.Наберіть останню програму і, використовуючи директиву trace, розгляньте послідовність задоволення вмонтованої цілі. 3.2.Напишіть предикат Прологу, який буде визначати позицію букви в алфавіті: alphabet-position (Letter, Position). Наприклад Position=1 якщо Letter=a т.д. 3.3.Напишіть програму Пролога, яка б визначала і друкувала значення n!. Значення n вводиться з клавіатури і є цілим. 3.4.Напишіть програму, яка знаходить найменше спільне кратне двох цілих чисел a i b (значення яких вводяться з клавіатури) НСК(a,b) , скориставшись формулою: , де НСД(a,b) позначає найбільший спільний дільник. Для знаходження НСД(a,b) використайте окремий предикат, який підключіть до вашої програми за допомогою директиви include. 4.КОНТРОЛЬ ПОШУКУ РІШЕНЬ. Пролог має два спеціальні предикати, які дозволяють вам контролювать механізм бектрекінгу: предикат fail, котрий примушує запускати механізм бектрекінгу, і cut (позначається !), який використовується для відміни бектрекінгу. 4.1.Використання предикату fail. Пролог запускає бектрекінг, коли чергове співставлення завершується невдачею. Предикат fail вироблює значення хибність, що позначає невдачу і примушує спрацьовувати бектрекінг. В наступному прикладі показано використання даного предикату для знаходження всіх можливих розв.язків. domains name = symbol predicates father(name, name) everybody clauses father(leonard, katherine). father(carl, jason). father(carl, marilyn). everybody :- father(X, Y), write(X, | is |, Y, |.s father |), fail. Зазначимо, що даремно використовувати підціль в тілі правила після fail . Враховуючи те, що значення fail є «хибність» (невдача), тому не має шляхів, які досягають підціль, яка знаходиться після предикату fail. 4.2.Відміна бектрекінгу. Предикат cut виробляє значеня істина, яке позначає успіх і позначається «!». Він розміщується в тілі правила в якості підцілі. Коли обробка досягає cut, він є завжди успішним і тому викликається наступна за ним ціль. Тому що cut був пройдений, не можливо провести бектрекінг підцілей, які розміщені перед cut в оброблюваному пункті і тому не можливо перейти до інших пунктів, які визначають поточний предикат. Існує два основних правила використання cut: 1.Коли ви знаєте попередньо, що певні варіанти ніколи не дадуть поштовху в знаходженні розв.язку, тоді використання cut(зелений cut) відкидає перегляд альтернативних шляхів. 2.Коли логіка програми потребує використання cut для відкидання перегляду альтернативних підцілей, тоді його називають червоним відтинанням. Іншими словами, предикат cut обмежує автоматичний перебір. Для багатьох задач виникає проблема, або ж обмеження бектрекінгу, або ж виключення його зовсім. Розглянемо спочатку програму, процес обчислень в якій містить непотрібний перебір. Нехай нам потрібно реалізувати функцію y=f(x), яка визначається наступним чином: якщо х < 10, тоді у = 10 . якщо 10 <= х і х < 20, тоді у = 20. якщо 20 <= х, тоді у = 30. На Пролозі її можна виразити наступною програмою: predicates f(integer,integer). clauses f(X,10):- X < 10. f(X,20):- X >= 10, X < 20. f(X,30):- X >= 20. Проаналізуємо, що буде робити програма, коли їй задати наступний запит: goal: f(5,Y), Y > 20. При обчисленні першою цілі f(5,Y), Y приймає значення 10, тому друга підціль стане 10 > 20. Вона закінчується невдачею. Але зрозуміло, що й ввесь список підцілей, який буде перевірятись завдяки бектрекінгу, також буде закінчуватись невдачею. Всі три правила обчислення функції f є взаємовиключними. Тому ми знаємо, що якщо успіх наступив в одному з них, немає необхідності перевіряти інші, бо вони приречені на невдачу. Отже, якщо в якійсь точці програми наступив успіх, для відміни непотрібного перебору, ми повинні явно вказати Пролог-системі, що не потрібно робити повернення із цієї точки. Це можна зробити за допомогою предикату cut(!). Попередня програма прийме вигляд: predicates f(integer,integer). clauses f(X,10):- X < 10,!. f(X,20):- X >= 10, X < 20,!. f(X,30):- X >= 20. Предикат cut не дає робити повернення із тих точок програми, в яких він поставлений і програма стала ефективнішою. Але, якщо ми побудуємо запит типу: goal: f(22,Y), тоді Пролог-система зробить три перевірки, і тільки після цього зв.яже з У значення 30. Але ж наші перевірки взаємовиключні. Тому для підвищення ефективності, ми можемо запропонувати такий варіант програми: predicates f(integer,integer). clauses f(X,10):- X < 10,!. f(X,20):- X < 20,!. f(X,30). В цьому випадку предикат відтинання міняє і декларативну сторону програми. Предикат cut по різному діє на складний запит і на множину фраз. Розглянемо випадок, коли предикат відтинання є однією із підцілей складного запиту: goal: a(X),b(Y),!,c(X,Y,Z) При виконанні цього запиту Пролог-система пройде через предикат cut тільки в тому випадку, коли підціль а(X) i підціль b(Y) будуть задоволені. Після того, як підціль cut буде оброблена, система не зможе повернутися назад для повторного розгляду підцілей |а| і |b|, якщо підціль |с| не задовільниться при поточних значеннях Х і У. Приведемо ще один приклад використання cut: predicates buy_car(symbol, symbol) car(symbol, symbol,integer) colors(symbol, symbol) clauses buy_car(Model, Color) :- car(Model, Color, Price), colors(Color, sexy),!, Price < 25000. car(maserati, green, 25000). car(corvette, black, 24000). car(corvette, red, 26000). car(porsche, red, 24000). colors(red, sexy). colors(black, mean). colors(green,preppy). Використання предикату cut говорить про те, що нас спочатку цікавить модель і колір автомобіля, а потім вже ціна. Для пояснення дії предикату cut повернемося до процесу керування побудови виведення в Пролозі. Нехай прологівська програма має наступний вигляд. р: - a,b. p: - c,d. Цю програму , використовуючи поняття процедури, можна прочитати наступним чином. При виконанні процедури р виконуються процедури a і b. Якщо вони закінчуються успішно, тоді і процедура р вважається успішно завершеною. Якщо це не так, тоді виконуються процедури с і d. Процедура р вважається задоволеною, якщо успішно виконуються процедури с і d. В іншому випадку процедура р закінчується невдало. Такий алгоритм обробки можна реалізувати на дереві типу «і» - «або» (мал.4.1), де ( позначає вузол типу «або», а ( позначає вузел типу «і». Р а b c d мал.4.1. Вершина типу «і» успішно розв.язувана тільки в тому випадку, коли її вершини сини успішно вирішені. Вершина типу «або» успішно розв.язувана в тому випадку, коли хоча б один з її вершин-синів успішно розв.язувана. Згідно стратегії пошуку в глибину, яка використовується в Пролозі, проводиться послідовний перегляд дерева «і - або» зверху - донизу , зліва - направо. Це відповідає виділенню самої лівої підцілі запиту і впорядкуванню зверху - донизу правил програми. Якщо при перегляді дерева якийсь з синів вершини типу «або» вирішується успішно, тоді обробка інших вершин синів (піддерева, яке знаходиться справа) призупиняється і вважається, що ця вершина типу «або» вирішилась успішно. Якщо якась з вершин синів вершини типу «і» вирішується невдало, тоді обробка інших вершин-синів її закінчується невдало. Потрібно відмітити, що обробка вершини «або» не закінчується, а лише призупиняється. Це пов.язано з тим, що з часом можливе повторне звернення до цієї вершини, і тоді гілки, які ще не аналізувалися, можуть знову привести до успіху в цій вершині (бектрекінг). Основна перевага такої стратегії - простота реалізації на послідовних машинах, недолік - великий перебір для деяких програм і запитів. До того ж , якщо дерево обчислень містить нескінченну гілку, тоді потрапивши на неї, ми не зможемо з неї вибратися і тому вірні відповіді, які лежать правіше від цієї вітки на дереві обчислень, не будуть знайдені. Одним із засобів усунення вказаного недоліку є використання предикату cut. Таким чином відтинається (і іноді досить суттєво) дерево розгалуджень. Розглянемо програму: а(x): - b(x), ! , c(x) a(x): - d(x) b(c). b(f) c(e) c(f) d(g) На запит a(Z) програма побудує єдину відповідь Z=e, оскільки вона не буде повертатися до розгалуджень, які виникли до звернення до cut (при обробці підцілей a(Z) і b(Z). Якщо ж ми видалимо предикат cut з першого правила і побудуємо запит a(Z), тоді отримаємо три відповіді Z=e, Z=f, Z=g. Зазначимо, що використання предикату cut робить програму ефективнішою, але програма позбавляється прозорої логічної семантики, залишається тільки процедурна семантика, яка відповідає вибраній стратегії перегляду дерева. Предикат cut (!) змінює стандартний порядок обчислень. При його виконанні, коли він стає самим лівим в запиті, забуваються (викидаються із стеку) всі розгалудження, зафіксовані з моменту звертання до правила, яке містить цей предикат, і далі проводиться повернення до попереднього розгалудження. 4.3.ПРЕДИКАТ NOT - заперечення як неуспіх. Розглянемо фразу |Ваня любить всі ігри крім баскетболу.| Попробуємо записати її на Пролозі. Першу частину цього твердження виразити легко: |Ваня любить довільне Х, якщо Х - гра|, або ж : like(wanja,X):-game(X). Aлe ж потрібно виключити баскетбол. Це можна зробити використавши інше формулювання: Якщо Х - баскетбол, тоді |Ваня любить Х| не буде істиною, інакше, якщо Х - гра, тоді |Ваня любить Х|. Для реалізації цього на Пролозі, використаємо предикат fail, який завжди закінчується невдало, вимагаючи закінчитися невдало і ту ціль, яка є її батьком: like(wanja, X):- basketball(X),!,fail. like(wanja, X):- game(X). Тут відтинання відкине із розгляду друге правило, коли гра - баскетбол, а fail викличе неуспіх. Цей приклад показує, що бажано мати унарний предикат not, такий що not(Ціль) буде істинним у випадку, коли Ціль не є істиною. На Пролозі його можна описати наступним чином: not(P):- P,!, fail. true. Пролог система має вмонтований предикат not, реалізований подібним чином. Тоді наш приклад можна переписати в такому вигляді: like(wahja,X):- game(X), not( basketball(X)). Наступна программа показує використання предикату not. Єдине, що потрібно відмітити, це те, що: предикат not виконується успішно, коли підціль не є істиною. Іншими словами, not виконується успішно, коли ассоційована з ним підціль не може довести істинність. domains name = symbol gpa = real predicates honor_student(name) student(name, gpa) probation(name) clauses honor_student(Name):- student(Name, GPA), GPA>=3.5, not(probation(Name)). student(|Betty Blue|, 3.5). student(|David Smith|, 2.0). student(|John Johnson|, 3.7). probation(|Betty Blue|). probation(|David Smith|). На запит honor_student(Name) вона видрукує список студентів, середній бал яких більший або ж дорівнює 3.5 за виключенням студентів Betty Blue і David Smith, які проходять випробувальний термін. 4.4.Труднощі у використанні відтинання і заперечення. Виділимо спочатку переваги використання відтинання: 1.За допомогою предикату cut можна підвищити ефективність програми. 2.Використовуючи cut, можна описати взаємовиключні правила, тому є можливість запрограмувати твердження: якщо умова P, тоді розв.язок Q, інакше розв.язок R. Обмеження на використання відтинання виходять із декларативної сторони прологівської програми. Якщо в програмі немає відтинання, тоді ми можемо міняти місцями порядок речень і цілей. Якщо ж предикат cut присутній в програмі, тоді зміна порядку речень в програмі може вплинути на її декларативний зміст (дати інший розв.язок). Якщо видалення відтинання з програми не міняє її декларативного змісту, тоді таке відтинання називають |зеленим|. В іншому випадку відтинання називають |червоним|. Працювати з запереченням також треба обережно. Труднощі виникають тому, що заперечення, яке ми використовуємо, не повністю відповідає математичному запереченню. Якщо ми побудуємо запит системі: goal: not(dog(baks)), вона, можливо, відповість |так|. Але цю відповідь не можна розуміти як повідомлення про те, що |Бакс не собака|, а потрібно трактувати те, що системі не вистачає інформації для доведення твердження | Бакс - собака|. Такий підхід бере свій початок від припущення про замкнутість світу. В відповідності до цього постулату світ замкнутий в тому розумінні, що все, що в ньому існує або ж вказане в програмі, або може бути із неї виведене. І в іншому випадку, якщо щось не міститься в програмі (не може бути з неї виведеним), тоді воно хибне, і відповідно буде істинним його заперечення. Ми ж традиційно не вважаємо світ замкнутим: якщо в програмі явно не сказано, що dog(baks), тоді це ще не значить, що ми хочемо сказати, що Бакс не собака. Приведемо ще один приклад обережного використання not: predicates r(symbol) g(symbol) p(symbol) clauses r(a). g(b). p(X):-not(r(X)). На запит goal: g(X), p(X) cистема відповість Х=b, а на запит goal: p(X), g(X) система відповість no (ні). Вся різниця заключається у тому, що в першому випадку змінна Х до моменту обчислення Р(X) була вже зв.язана, а в другому випадку цього ще не трапилось. 4.5.Засоби керування. Факти та правила Прологу отримують інформацію, якщо вони викликаються з аргументами, які є або ж константами, або ж зв.язаними змінними. Вони повертають інформацію в процедуру виклику шляхом зв.язування змінних аргументів, які не були зв.язані. Унифікація - це процес обробки на співпадання двох предикатів і призначення вільних змінних. Вона включає наступні кроки: 1.Пролог пробує задовільнити ціль. починаючи з початку програми шукати відповідність. 2.Коли запитується новий виклик, пошук також починається з початку програми. 3.Коли виклик знаходить успішно відповідність (кажуть виклик повертається), викликається наступна підціль. 4.Якщо змінні зв.язані в підпункті, тоді єдиний шлях звільнить їх - бектрекінг. Можна виділити чотири основні пункти бектрекінгу: 1.Підцілі повинні бути задоволені в послідовності зверху вниз. 2.Пункти предикату тестуються в тому порядку, в якому вони з.являються в програмі при перегляді зверху - вниз. 3.Ціль буде задоволена, якщо буде знайдена відповідність для кожного рівня відповідного дерева. 4.Виклик, який породжує множину рішень, є недетермінованим. 4.6.Узагальнення. 1.Пролог має три предикати для контролю напрямку логічного пошуку вашої програми: * fail є завідомо невдачею. За допомогою його включається механізм бектрекінгу для пошуку альтернативних рішень. * not приймає значення істина, коли для асоційованої з ним підцілі не може бути доведено істинність. * cut - виключає бектрекінг. 2.Можна розглядати, що правила Прологу є визначеннями процедур з точки зору процедурної перспективи. З точки зору процедурної перспективи, правила можна розглядати як варіанти оператору case Паскалю. Вправи. 4.1.Нехай маємо програму p: - a, b. p: - c. Декларативна сутність якої наступна: р буде істинним тоді і тільки тоді, коли будуть істинні одночасно і а і b, або буде істинним с. Яким буде декларативна сутність програм? а) р: - а, ! , b. p: - c б) р: - с р: - a, ! , b. 4.2.Наступні відношення розподіляють числа на три класи - додатні, нуль і від.ємні: клас (Число, додатні): - Число>0. клас (0, нуль). клас (Число, від.ємні): - Число<0. Зробіть цю процедуру більш ефективною за допомогою відтинання. 4.3.Нехай маємо програму р(4) р(5): - ! р(6). Напишіть відповіді пролог-системи на наступні питання: а) goal: p(X). б) goal: p(X), p(Y). c) goal: p(X), !, p(Y) 4.4.Напишіть програму знаходження максимума двох чисел, використовуючи предикат відтинання. 5.ПРОСТІ ТА СКЛАДНІ ОБ.ЄКТИ. В цій лекції ми розглянемо весь спектр даних, починаючи з простих і закінчуючи складними даними, які будуються з простих. 5.1 Прості дані. В якості простих даних виступають змінні або ж константи. Константа може бути або ж символьною (char), або ж числовою (integer, real), атомарною (symbol, string). Змінна позначається ідентифікатором. Ідентифікатор починається з великої букви у діапазоні від А до Z, або ж символом підкреслення (_). Як ми вже зазначали, єдиний символ підчеркування позначає анонімну змінну. В Пролозі змінна може зв.язуватись з любим допустимим аргументом або об.єктом даних. Відмітимо, що змінні Прологу є локальними, а не глобальними. Іншими словами, якщо два пункти мають змінну Х, тоді ці Х є різними змінними. 5.1.1. Константи як об.єкти даних. Константи включають символи, числа і атоми. Значення константи міститься в її імені. Так константа 2 може символізувати тільки число 2, а константа abracadabra може символізувати тільки стрічку abracadabra. Символи. Символи мають тип char, вони будуються з символів коду ASCII. Існує два способи задання символів в якості констант Прологу: безпосередньо, або ж з попереднім символом (). Ось приклад деяких друкованих символів: .f., .4.,.F.. Якщо ж вам потрібно написати символи типу (), (|), (.), тоді перед ними потрібно поставити символ (): (.\.), (.|.), (...). Деякі пари символів позначають спеціальні дії, наприклад: . .-перехід на нову стрічку. . .-повернення каретки. . .-горизонтальна табуляція. Числа. Числа мають тип або іnteger, або real. Цілі містять значення з діапазону від -32768 до 32767 включно. Дійсні зберігаються в форматі ІEEE в проміжку від 1е-308 до 1е308. Атоми. Атом має тип або ж symbol, або ж string. Пролог виконує автоматичне перетворення типів між цими двома доменами. Ім.я символьних атомів починається з маленької букви. Стрічкові атоми повинні заключатись в подвійні лапки і можуть містити любу комбінацію дозволених символів PDC Прологу. 5.2.Складні об.єкти даних і функтори. Складні об.єкти даних дозволяють вам заключати декілька частин інформації в єдиний пункт. Наприклад, дата 2 квітня 1994 складається з 3 частин. Але іноді їх корисно з.єднати воєдино: date(|April|,2,1989) Так виглядає факт Прологу, в даному випадку - просто об.єкт даних. Він починається з імені або ж функтора (в нашому прикладі date). Функтор не символізує якесь обчисленя, яке повинно бути виконаним. Це просто ім.я об.єкту. Аргументи складного об.єкту самі можуть бути складними об.єктами. BIRTHDAY / / person date ( / / ! ..Joe.. ..Jones.. ..Aug..20 1918 або ж birthday(person(..Joe..,..Jones..),date(..Aug..,20,1918)) 5.2.1.Уніфікація складних об.єктів. Складний об.єкт може уніфікуватись або ж з простою змінною, наприклад, data(..April..,2,1981) зрівнюється з X і зв.язує X з date(«April»,2,1981), або ж з складним об.єктом, який співпадає з ним структурно: так data(..April..,2,1981) зрівнюється з date(Mo,Da,Yr). Використання знаку дорівнює для уніфікації складних об.єктів. Пролог проводить уніфікацію в двох місцях. По перше, уніфікація проходить, коли є виклик співставлення голови фрази. Інший спосіб виконання уніфікації - це використання знаку (=). В цьому випадку Пролог буде ототожнювати об.єкти, які знаходяться з обох сторін знаку. Цей підхід є корисним для знаходження значень аргументів складного об.єкту. Наприклад, наступна програма виконує такі дії. Якщо дві особи мають одне й теж прізвище, тоді другій особі приписується адреса першої особи. domains person = person(name,address) name = name(first,last) address = addr(street,city,state) street = street(number,street_name) city,state,street_name = string first,last = string number = integer goal P1 = person(name(jim,mos), addr(street(5,|1stst|),igo,|CA|)), P1 = person(name(_,mos),Address), P2 = person(name(jane,mos),Address), write(P2). Складні об.єкти можуть бути переглянуті і перетворені в прості об.єкти фраз вашої прологівської програми, що значно спрощує програмування. Наприклад , розглянемо факт: owns(john,book(.From Here to Eternity.,.James Jones.)), в якому ми стверджуємо, що Джон має книгу .З теперішнього в майбутнє., яку написав Джеймс Джонс. Подібно ви можете написати: owns(john,horse(blackly)), який можна було б інтерпретувати так: Джон має коня, якого кличуть blacky. Складними об.єктами в цих прикладах будуть: book(.From Here to Eternity.,.James Jones.) і horse(blacky). Якщо написати два факти: owns(john,.From Here to Eternity.). owns(john,blacky). тоді ви при традиційному запиті не зможете відрізнити : blacky буде назвою книги чи кличкою коня. З іншого боку ми можемо використати в якості першої компоненти складного об.єкту функтор, для розмежування різних об.єктів. Для цього прикладу бажано було б використати функтори книги і коня. 5.2.2.Приклад застосування функторів. Не тільки аргументи, а також функтор може нести корисну інформацію, якщо ви визначаєте домейн з декількома альтернативними функторами. Розглянемо типічну задачу зсуву курсора на екрані терміналу. Ви можете заключити, що предикат повинен мати два аргументи: напрямок зсуву і відстань зсуву. В Пролозі ці аргументи можуть бути простими об.єктами. Програма, зображена на малюнку 5.1, демонструє як це можна зробити. Вона використовує предикат cursor(Row,Column), який робить дві речі: 1)інформує де знаходиться курсор, коли аргументи його вільні. 2)розміщує курсор у відповідну стрічку і стовбець екрану згідно значень аргументів. domains row, column, step = integer movement = up(step). down(step). left(step). right(step) predicates move_cursor(row, column, movement) clauses move_cursor(R, C, up(Step)) :- cursor(R, C), R1=R-Step, cursor(R1, C). move_cursor(R, C, down(Step)) :- cursor(R, C), R1=R+Step, cursor(R1, C). move_cursor(R, C, left(Step)) :- cursor(R, C), C1=C-Step, cursor(R, C1). move_cursor(R, C, right(Step)) :- cursor(R, C), C1=C+Step, cursor(R, C1). мал.5.1. 5.3.Приклад використання складних об.зктів. Інша важлива властивість складного об.єкту дозволяє просто розглядати групу значень як один аргумент. Припустимо, що ви створюєте телефонний довідник у вигляді бази даних. В нього ви хочете занести номера телефонів друзів з датою їх народження. Для цього достатньо розглянути секцію: predicates birthday (( Month Day Year clauses phone( concretic values). phone( concretic values). Перші 5 аргументів предикату можуть бути представлені у вигляді двох складних об.єктів типу: person / First name Last name Які ми можемо реалізувати у вигляді відношeнь: person(First_name,Last_name) birthday(Month,Day,Year) Тоді ми можемо написати програму, яка дуже легко читається. domains name= person(sym,sym) birthday=b_data(sym,integer,integer) ph_numb = sym predicates phone_list(name,ph_numb,birth_day) clauses phone_list(person(ed,willas),..422-324..,b_data(...)). phone ..... Вона також зручна для модификації. Наприклад, додавши до нашої програми кілька правил, ми можемо створювати список людей, день народження яких належить поточному місяцю (стандартний предикат data бере з комп.ютерного годинника поточну дату). domains name = person(symbol, symbol) /* (First, Last) */ birthday=b_date(symbol,integer,integer) /*(Month, Day,Year)*/ ph_num = symbol /* Phone_number */ predicates phone_list(name, symbol, birthday) get_months_birthdays convert_month(symbol, integer) check_birthday_month(integer, birthday) write_person(name) clauses get_months_birthdays:- makewindow(1,7,7, | This Month.s Birthday List |, 0, 0, 25, 80), write(| First name Last Name |), date(_, This_month, _), phone_list(Person, _, Date), check_birthday_month(This_month, Date), write_person(Person), fail. get_months_birthdays :- write(| Press any key to continue: |), readchar(_). write_person(person(First_name, Last_name)):- write(| |,First_name, | |, Last_name), nl. check_birthday_month(Mon, b_date(Month, _, _)) :- convert_month(Month, Month1), Mon = Month1. phone_list(person(ed, willis), |767-8463|, b_date(jan, 3, 1955)). phone_list(person(benjamin, thomas), |438-8400|, b_date(feb, 5, 1985)). phone_list(person(ray, william),|555-5653|, b_date(mar, 3,1935)). phone_list(person(thomas, alfred), |767-2223|, b_date(apr, 29, 1951)). phone_list(person(chris, grahm), |555-1212|, b_date(may, 12, 1962)). phone_list(person(dustin, robert), |438-8400|, b_date(jun, 17, 1980)). phone_list(person(anna, friend), |767-8463|, b_date(jun, 20, 1986)). phone_list(person(brandy, rae),|555-5653|, b_date(jul, 16, 1981)). phone_list(person(naomi, friend), |767-2223|, b_date(aug, 10, 1981)). phone_list(person(christina, lynn), |438-8400|, b_date(sep, 25, 1981)). phone_list(person(kathy, ann), |438-8400|, b_date(oct, 20, 1952)). phone_list(person(elizabeth, ann), |555-1212|, b_date(nov, 9, 1984)). phone_list(person(aaron, friend), |767-2223|, b_date(nov, 15, 1987)). phone_list(person(jennifer, caitlin), |438-8400|, b_date(dec, 31, 1981)). convert_month(jan, 1). convert_month(feb, 2). convert_month(mar, 3). convert_month(apr, 4). convert_month(may, 5). convert_month(jun, 6). convert_month(jul, 7). convert_month(aug, 8). convert_month(sep, 9). convert_month(oct, 10). convert_month(nov, 11). convert_month(dec, 12). Як працює програма? 1. Спочатку, програма робить вікно на екрані дисплею для відображення результату. 2. Після, вона друкує заголовок у вікно, для полегшення інтерпретації результату. 3. Далі, в предикаті get_month_birthday за допомогою вмонтованого предикату date отримуємо значення поточного місяця. 4. Після, програма робить пошук по базі даних списку людей, які народилися в поточному місяці. Знаходиться перша особа в базі даних. Виклик предикату phone_list(Person,_,Date) зв.язує ім.я і прізвище цієї особи з змінною Pеrson для співставлення функтору person з змінною Person. Виклик також зв.язує день народження цієї особи з змінною Date. Відмітимо, що вам досить використання однієї змінної для запам.ятовування повного імені особи і однієї змінної для запам.ятовування повної дати дня народження. Це результат використання складних об.єктів. 5. Зараз програма може обробляти день народження особи, використовуючи змінну Date. Така обробка починається в наступній підцілі, де програма обробляє поточний місяць, який заданий числом і день народження особи в предикаті check_birthday_month. 6. Звернемо увагу на те, як цей процес проходить. Пролог викликає предикат check_birthday_month з двома змінними: перша змінна зв.язана з цілим, а друга - з функтором і його трьома аргументами. В голові правила, де визначається предикат check_birthday_month перший аргумент This_month зрівнюється з змінною Моn. Другий аргумент Date співставляється з b_date(Month,_,_). Це добре, оскільки він є тим же значенням об.єкту даних, яке ви обробляєте. Оскільки всі наші дії пов.язані тільки з місяцем народження особи, в якості дня і року народження можуть виступати анонімні змінні. 7. Предикат check_birthday_month спочатку конвертує символьне позначення місяця в числове значення. Після, Пролог може порівняти значення поточного місяця з значенням місяця народження особи. Якщо порівняння задовольнилось, обробка може закінчуватись. Тому далі стоїть підціль fail. В іншому випадку Пролог-система починає бектрекінг для пошуку іншого розв.язку. 8.Наступна підціль write_person друкує повне ім.я особи до списку осіб, день народження яких належить поточному місяцю, підціль fail форсує бектрекінг. 5.4.Опис доменів складних об.єктів. В цій секції ми покажемо як визначаються домени для складних об.єктів. Після компілювання програми, яка містить наступні відношення: owns(john,book(.From Here to Eternity.,.james Jones.)). і owns(john,horse(blacky)). ми можемо системі задати запит goal:owns(john,X). Змінна X після цього може бути зв.язана з різними типами об.єктів: книгою, конем, або ж можливо іншим об.єктом, який ви визначили. Це випливає із нашого визначення предикату owns. Тому нам не бажане старе використання предикату: owns (symbol,symbol). Замість нього ми мусимо сформулювати нове визначення предикату, наприклад: owns(name,articles) Зараз, ми можемо описати об.єкт articles в секції domains наступним чином: domains articles=book(title,author). horse(name) title,author,name=symbol Крапка з комою читається тут як |або|. В цьому випадку можливі альтернативи: книга може ідентифікуватись назвою і автором. або ж кінь ідентифікується своєю кличкою. Всі об.єкти title , аuthor, name є стандартними, символьного типу. До опису об.єктів може бути добавлено і більше альтернатив. Наприклад, articles може бути судновою книгою, або ж банківською книгою. У випадку суднової книги можемо використати функтор без аргументів, банківську книгу можемо описати як bankbook(balance). В цьому випадку об.єкт articles може бути описаний: articles =book(title,author). horse(name). boat. bankbook(balance) title,author,name = symbol balance =real Далі приведемо повну програму, яка демонструє використання в фактах, що описуються предикатом owns, складного об.єкту типу articles: domain articles = book(title, author) . horse(name) . boat . bankbook(balance) title, author, name = symbol balance = real predicates owns(name,articles) clauses owns(john, book(|A friend of the family|, |Irwin Shaw|)). owns(john, horse(blacky)). owns(john, boat). owns(john, bankbook(1000)). Тепер відкомпілюємо нашу програму. Коли ми задамо системі запит: goal: owns(john,Thihg). Вона видасть чотири рішення: Thing = book(.A friend of the family.,.Irwin Shaw.) Thing = horse(blacky) Thing = boat Thing = bankbook(1000.) 4Solutions Таким чином, опис домену складного об.єкту в загальному має такий вигляд: domain object= alter1(D,D,...). alter2(D,D,...). ... де alter1 і alter2 довільні, але різні функтори. Позначення (D,D,...) задає список імен доменів, які або ж описані десь в іншому допустимому місці, або ж мають один із стандартних типів. Відмітимо наступне: 1. Альтернативи розділяються крапкою з комою. 2. Кожна альтернатива має функтор і можливо список доменів для відповідних аргументів. 5.5.Багаторівневі складні об.єкти. Пролог дозволяє нам конструювати складні об.єкти на декількох рівнях. Наприклад, в предикаті book(.The Ugly Duckling...Andersen.) замість використання прізвища автора, ми хочемо використати нову структуру, яка більш детально описує автора, включаючи до попередньої інформації ще й ім.я. Для виклику функтору результуючого нового складного об.єкту, ми повинні змінити базовий опис книги: book(.The Ugly Duckling.,author(.Hans Christian.,.Andersen.)) В старому описі об.єкту: book(title,author) другий аргумент функтору book є author. Але старий опис author = symbol може тільки включати просте ім.я, тому його не можна застосовувати. Ми повинні зараз специфікувати, що author є складним об.єктом, який включає ім.я та прізвище: author(first_name,last_name) Котре вимагає наступний опис: domains articles = book(title, author) . horse(name) . boat . bankbook(balance) author = author(first_name,last_name) title, author, name = symbol balance = real Коли використовуються складні об.єкти різного рівня, їх зручно зображати у вигляді дерева. book / title author / / firstname lastname Речення домену описує тільки один рівень дерева, а не все дерево. Наприклад, книга з нашого прикладу не може бути описана наступним чином. book=book(title,author(firstname,lastname)) 5.6.Приклад, який ілюструє задання структури речення англійської мови. Розглянемо приклад задання граматичної структури речення, використовуючи складний об.єкт. Найбільш просте речення має підмет і присудкову частину: sentence = sentence(noun,verbphrase) Де підмет є простим словом: noun=noun(word), а присудкова частина може мати або ж дієслово з пояснюючою частиною, або ж просто дієслово verbphase=verbphrase(verb,noun). verb(word) verb = verb(word) Використовуючи такий опис, речення .Еllen owns the book.. може бути представлене sentence(noun(ellen),verbphrase(verb(owns),noun(book))) Відповідне дерево прийме вигляд sentence / / noun verbphrase / / / verb noun | | | ellen owns the book Подібний підхід може бути використаний при написанні блоку синтаксичного аналізу компілятора. 5.7.Опис змішаних складних об.єктів. В цьому розділі ми розглянемо три різні типи опису доменів, які ви можете використовувати у ваших програмах. Ці описи дозволяють вам використовувати предикати, які: мають аргумент , який може бути різного типу. мають змінну кількість аргументів, кожний з яких окремого типу. мають змінну кількість аргументів, деякі з яких можуть бути різного типу. 5.7.1.Аргументи, які можуть мати різний тип. Для того, щоб дозволити предикату допустити аргументи різного типу, ви повинні додати опис функтору. Наприклад, в наступному прикладі фраза your_age, буде допускати аргумент типу age, який може бути стрічковим, цілим, дійсним. predicates your_age(age) clauses your_age(i(AGE)):-write(AGE) your_age(r(AGE)):-write(AGE) your_age(s(AGE)):-write(AGE) тоді домен повинен бути наступним: domains age = i(integer). r(real). s(string) predicates your_age(age) Поряд з тим Пролог не дозволяє наступні описи доменів: domain age = integer, real, string 5.7.2 Cписковий тип. Припустимо, нам необхідно створити базу-довідник, в якій ми будемо зберігати дані про лекційні курси, які можуть читати професори. Її можна реалізувати наступною програмою: predicates teacher(symbol, symbol, symbol) clauses teacher(ed,willis,english). teacher(ed,willis,math1). teacher(ed,willis,hystory1). teacher(mary,marker,english2). teacher(mary,marker,math2). teacher(cris,grim, geometry). Тут в нас виникає необхідність повторювати прізвище для кожного предмету. Це марудно, тому краще використати тип списку. В наступному прикладі, аргумент classes, описаний як списковий тип. domains classes = symbol* predicates teacher(symbol,symbol, classes) clauses teacher(ed, willis,[ english,math1, history1]). teacher(mary, maker,[history2, math2 ]). teacher(chris,grahm,[geometry]). В цьому прикладі відмітимо опис DOMAINS : domains class = symbol* Тут ми показуємо, як представляються в Пролозі списки. Символ (*) означає, що class є символьним списком. Аналогічно можна визначити список цілих чисел: domains integer_list = integer* 5.8.Порівняння складних об.єктів. Складні об.єкти повинні зрівнюватись на еквівалентність з предикатами, визначеними програмістом, подібно до предикату are_equal із наступної програми: domains d = pair(integer, integer) . single(integer) . none predicates are_equal(d, d) clauses are_equal(X, X). Задамо ціль goal: are_equal(5,4). Бачимо помилку в визначенні домену. Для фіксації проблеми додамо опис: are_equal(integer, integer). 5.9.Узагальнення. 1.Програма Прологу може містити наступну множину типів даних: простий або складний, стандартний або визначений користувачем. 2.Складні структури даних дозволяють об.єднувать окремі частини інформації в один об.єкт. Він складається з імені (функтора) і одного або більше аргументів. 3.Функтор Прологу не відповідає функціям традиційних мов програмування типу Паскаль. Він не викликає ніякої дії. 4.Складна структура даних може уніфікуватись з простою змінною, або з складним об.єктом, який має відповідну структуру. Знак «=« використовується для уніфікації складних об.єктів. Вправи. 5.1. Виберіть деяку форму задання бази даних, в якій містяться повідомлення про операції з кредитними карточками. Кожний запис повинен мати інформацію про прізвище особи, яка тратить гроші, про тип операції і кількість грошей. Напишіть програму, яка буде видавати значення кінцевої суми всіх операцій для конкретної особи. 5.2. Нехай нам потрібно створити базу даних про сім.ї, яка б дозволяла оперувати з наступною інформацією. Кожна сім.я складається з трьох компонент: чоловік, дружина і діти. Оскільки кількість дітей в різних сім.ях може бути різною, тому бажано їх задавати у вигляді списку, який складається з довільної кількості елементів. Кожного члена сім.ї в свою чергу можна задати структурою, яка складається з чотирьох компонент: ім.я, прізвище, дата народження і місце роботи. Інформація про роботу може бути такою - це або «не працює», або вказівка на місце роботи і заробітної плати. Напишіть терм, який би дозволяв: а)посилатись на всіх Іванових. б)посилатись на всі сім.ї, які мають трьох дітей. Побудуйте запит: а)який би дозволяв знаходити всіх заміжніх жінок, які мають не менше трьох дітей. Побудуйте набір предикатів, який би дозволив використати наступні запити до бази даних: а)знайти всіх людей із бази даних. b)знайти всіх дітей, які народились в 1990 році. с)знайти всіх дружин, які працюють. g)знайти людей, які народились до 1960 року. е)знайти загальний заробіток кожної сім.ї. 6. ІТЕРАЦІЯ І РЕКУРСІЯ. 6.1.Реалізація ітераційного процесу за допомогою бектрекінгу. В цьому розділі ми розглянемо спочатку організацію циклічної обробки, а потім рекурсивні структури даних. Пролог допускає тільки два типи повторних дій: бектрекінг і рекурсію. В програмі, зображеній на мал.6.1, показано використання бектрекінгу для реалізації циклу. На поставлений запит будуть друкуватись всі можливі рішення. predicates country(symbol) print_countries clauses country(england). country(france). country(germany). country(denmark). print_countries :- country(X), write(X), /* write the value of X */ nl, /* start a new line */ fail. print_countries. мал.6.1. Перша фраза говорить: |Знаходячи розв.язок предикату cuntry(x), надрукувати країну Х і перейти на нову стрічку.» Потім викликається предикат fail. В цьому випадку fail позначає наступне: якщо розв.язок поставленої цілі ще може бути знайдений, тоді повернутись і пошукати альтернативний розв.язок. Вмонтований предикат fail завжди має хибне значення, але ми могли б форсувати бектрекінг, використавши якийсь інший, завжди хибний предикат типу 10 = 3 + 4, або country(abracadabra) . Таким чином, будуть надруковані всі країни і процес обробки системою першої фрази закінчиться. Після, почнеться обробка другої фрази того ж предикату print-countries. Вона нічого не робить, а тільки завершає успіхом роботу системи. Кінцеве виведення буде мати вигляд: england france germany denmark Yes Якби не було другої фрази, виведення закінчувалось - No, а все інше виведення залишилось без змін. 6.2.Дії типу до і після. Можливо в попередній програмі треба для наглядності зробити наступні зміни: 1. надрукувати заголовок. 2. надрукувати всі можливі розв.язки запиту. 3. надрукувати в кінці заключне повідомлення. Тоді нам потрібно в попередню програму внести наступні модифікації в визначенні предикату Print-countries. print_countries:- write(|Some delightful places to live are|), nl, fail. print_countries:- country(X), write(X), nl, fail. print_countries:- write(| And maybe others.|), nl. 6.3.Застосування бектрекінгу для реалізації циклів. ( repeat. Розглянемо наступний предикат ( ( repeat:-repeat. Такий трюк дозволяє реалізувати управляючу структуру, яка дозволяє отримати нескінченну кількість рішень. Більш детально можна зрозуміти її роботу після вивчення поняття хвостової рекурсії. Для прикладу розглянемо наступну програму. predicates repeat typewriter clauses repeat. repeat :- repeat. typewriter :- repeat, readchar(C), write(C), char_int(C,13). Ця програма показує як працює repeat. Правило typewriter... описує процедуру, яка отримує символи з кейборди і друкує їх на екрані, поки не буде натиснута клавіша ENTER (ASCII кoд 13). Вона працює так: 1.Виконається repeat (який нічого не робить). 2.Потім читається символ в змінну C. 3.Потім друкується C. 4.Потім перевіряється чи С не дорівнює 13 в коді ASCII. 5.Якщо так, тоді фінішуємо. Інакше, починається бектрекінг і перегляд альтернатив. Ні write ні readchar не генерують альтернативних рішень, тому бектрекінг веде до repeat, котрий дозволяє отримати альтернативні рішення. 6.Тепер обробка може повернутись знову на початок, читати інший символ, друкувати його, перевіряти на рівність 13. 6.4.Рекурсивні процедури. Інший шлях реаліцації повторення є використання рекурсії. Розглянемо рекурсивну програму обчислення значення факторіалу n!. Яку можна проінтерпретувати наступним чином. Якщо n=1, тоді n!=1 (за рахунок factorial(1,1):-!), інакше n!=n*(n-1)!. Останнє обчислення забезпечується наступною фразою визначення factorial(x,FactX). predicates factorial(integer, real) clauses factorial(1, 1) :- !. factorial(X, FactX) :- Y = X-1, factorial(Y, FactY), FactX = X*FactY. 6.5.Використання аргументів в якості параметрів циклу. Попередня рекурсивна програма обчислення факторіалу може бути описана на Паскалі в наступному ітераційному вигляді: p:=1. for i:=1 to n do p:=p*i. FacN:=p. або ж використовуючи цикл типу while: p:=1. i:=1. while i<=n do begin p:=p*i. i:=i+1 end. FacN:=p. Мал.6.2. Фрагмент програми, зображений на мал.6.2, можна транслювати в Пролог наступним чином. predicates factorial(integer, real) factorial_aux(integer,real, integer, real) /* Числа більші за 32767 повинні бути описані як дійсні. */ clauses factorial(N, FactN):- factorial_aux(N, FactN, 1, 1). factorial_aux(N, FactN, I, P):- I <= N, !, NewP = P * I, NewI = I + 1, factorial_aux(N, FactN, NewI, NewP). factorial_aux(N, FactN, I, FactN) :- I > N. Мал.6.3. Більш красивіший варіант попередньої програми поданий на мал.6.4. predicates factorial(integer,real) factorial(integer, real,integer, real) clauses factorial(N,FactN):- factorial(N,FactN,1,1). factorial(N, FactN, N, FactN):- !. factorial(N, FactN, I,P):-NewI = I+1, NewP = P*NewI, factorial(N,FactN,NewI,NewP). мал.6.4. 6.1. Написати рекурсивну і нерекурсивну програми, які обчислюють значення F(M,N) для довільної пари цілих чисел M,N>=0, яке визначається наступним чином: ( M+N+1 якщо M*N=0 F(M,N)=( ( F(M-1, F(M,N-1)) в іншому випадку 6.2. N-те число Фіббоначі визначається наступним чином ( 0 якщо N=0 F(N)=( 1 якщо N=1 ( F(N-1)+F(M,N-1)) в іншому випадку Написати рекурсивну і некурсивну програми, які обчислюють N-те число Фіббоначі. 6.3. Найбільший спільний дільник G(M,N) двох цілих чисел M і N можна визначити наступною рекурсивною схемою ( M якщо N=0 G(M,N)=( ( G(N, MOD(M,N)) якщо N(0 Написати програму, яка використовує рекурсивно-визначений предикат G(M,N), для визначення найбільшого спільного дільника декількох пар чисел. 7. РЕКУРСИВНІ СТРУКТУРИ ДАНИХ. Рекурсивними можуть бути не тільки правила, а й структури даних. Пролог належить до тих мов програмування, в яких дуже зручно можна організовувати, описувати і реалізовувати дані рекурсивного типу. Тип даних буде рекурсивним, якщо він представляє собою структуру, яка в своєму визначенні використовує структуру, подібну собі. Найбільш використовуваною рекурсивною структурою є список, але ми його розглянемо трішки пізніше. В цьому розділі ми зосередимо свою увагу на структурі даних типу дерева і на її використанні. 7.1.Структура даних типу дерева. Серед структур даних типу дерева можна виділити спеціальний клас найбільш вживаних дерев- бінарні дерева. Можна дати наступне рекурсивне визначення бінарного дерева: 1.Пусте дерево- бінарне дерево. 2.Кожний вузел бінарного дерева має не більше одного лівого бінарного піддерева і не більше одного правого бінарного піддерева. Таку структуру даних в Пролозі можна визначити за допомогою двох предикатів: treetype = tree(string,treetype,treetype) та empty Останній використовується для позначення пустого дерева. Тому структура даних для задання бінарного дерева може бути описана наступним чином: domains treetype= tree(string, treetype,treetype). empty Наприклад, дерево зображене на мал.7.1 c a t h y / / m i c h a e l m e l o d y / / / / c h a r l e s h a s e l j i m e l e o n o r Мал.7.1. може бути описане: tree(.Cathy.,tree(.Michael.,tree(.Charles.,empty, empty), tree(.Hazel. ,empty, empty)), tree(.Melody., tree(.Jim.,empty, empty), tree(.eleanor. ,empty, empty))) Відмітимо, що це не є прологівсьгою фразою. це є тільки складною структурою даних. 7.2.Обходи дерева. Існує багато правил обходу дерев: прямий, зворотній, кінцевий і т.д.. Наприклад, розглянемо алгоритм прямого обходу. 1. Якщо дерево пусте, тоді нічого не робити. 2. В іншому випадку, обробити поточний вузел, потім обійти ліве піддерево обробленого вузла, а потім обійти праве піддерево обробленого вузла. В Пролозі його можна реалізувати за допомогою двох фраз: traverse(empty). traverse(tree(X,Y,Z):- do something with X, traverse(Y), traverse(Z). Для того, щоб подивитись на нього в дії, розглянемо програму, зображену на мал.7.2, яка обходить дерево і друкує значення, що містяться в вузлах дерева. domains treetype = tree(string, treetype, treetype). empty() predicates print_all_elements(treetype) clauses print_all_elements(empty). print_all_elements(tree(X,Y,Z)):- write(X), nl, print_all_elements(Y), print_all_elements(Z). goal: print_all_elements(tree(|Cathy|, tree(|Michael|, tree(|Charles|, empty, empty), tree(|Hazel|, empty, empty)), tree(|Melody|, tree(|Jim|, empty, empty), tree(|Eleanor|, empty, empty)))). Мал.7.2. 7.3.Створення дерева. Для багатьох задач виникає потреба створення структури даних типу дерева в пам.яті комп.ютера з подальшою її обробкою. Створити один вузел дерева тривіально: create_tree(N, tree(N,empty,empty)). Цей предикат можна інтерпретувати: |Якщо N є елементом даних, tree(N,empty,empty) є вузлом дерева,який містить цей елемент. Процес побудови дерева трохи складніший. Розглянемо наступну фразу, яка містить предикат з трьома аргументами типу дерева. Він вставляє перше дерево в якості лівого піддерева другого дерева, використовуючи третє дерево як результуюче. insert_left(X, tree(A, _ , B), tree(A,X,B)). Припустимо, наприклад, що ми хотіли б вставити tree(.Michael . , empty, empty) в якості лівого піддерева tree(.Cathy., empty, empty). Це можна зробити, сформувавши запит: goal : insert_left(tree(.Michael.,empty,empty), tree(.Cathy.,empty,empty), T) де T зразу ж прийме значення tree(.Cathy., tree(Michael.,empty,empty), empty). Таким чином, ми поетапно можемо побудувати дерево. Програма, зображена на мал.7.3., демонструє використання запропонованого підходу для побудови дерева. На практиці, елементи, які розміщуються в вузлах дерева, майже завжди беруться з зовнішнього файлу. /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Прості процедури побудови дерева. * *create_tree(A, B) вставляє A в поле даних дерева B * * insert_left(A, B, C) вставляє A в якості лівого піддерева B, * * отримуючи дерево C * * insert_right(A, B, C) вставляє A в якості правого піддерева B, * * отримуючи дерево С * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ domains treetype = tree(string, treetype, treetype). empty() predicates create_tree(string, treetype) insert_left(treetype, treetype, treetype) insert_right(treetype, treetype, treetype) clauses create_tree(A, tree(A, empty, empty)). insert_left(X, tree(A, _, B), tree(A, X, B)). insert_right(X, tree(A, B,_), tree(A, B, X)). goal : /* Спочатку створимо вузли (однорівневі дерева)... */ create_tree(|Charles|, Ch), create_tree(|Hazel|, H), create_tree(|Michael|, Mi), create_tree(|Jim|, J), create_tree(|Eleanor|, E), create_tree(|Melody|,Me), create_tree(|Cathy|, Ca), /* ... потім встановимо зв.язки */ insert_left(Ch, Mi, Mi2), insert_right(H , Mi2, Mi3), insert_left(J, Me, Me2), insert_right(E , Me2, Me3), insert_left(Mi3,Ca, Ca2), insert_right(Me3, Ca2, Ca3), /* ... і роздрукуємо результат. */ write(Ca3), nl. Maл.7.3. Тому, що в Пролозі ми не можемо змінити значення змінної, а можемо тільки зв.язати змінну з якимсь значенням, Програма з мал.7.3 має стільки багато змінних. 7.4.Бінарний пошук на дереві. Ми описали використання дерева для задання відношень між його елементами. Це не кращий спосіб використання дерева в Пролозі, оскільки люба фраза Прологу може зробити подібну роботу. Але використання дерева має інші переваги. Розглянемо спеціальний тип бінарного дерева, яке називають бінарним деревом пошуку. Воно будується наступним чином: 1.Якщо поточний вузел є пустим деревом, тоді вставити елемент в нього. 2. В іншому випадку, зрівняти елемент, що вставляється з елементом, який зберігається в поточному вузлі. Якщо значення нового елементу менше, тоді вставити новий елемент в ліве піддерево поточного вузла, а в іншому випадку - вставити в праве піддерево поточного вузла. Прологівська реалізація побудови бінарного дерева пошуку буде вимагати наявності трьох фраз. Перша insert(NewItem,empty, tree(NewItem,empty,empty):-!. позначає, |результатом вставки елементу NewItem в пусте дерево буде дерево tree(NewItem, empty,empty) |. Друга й третя фрази реалізовують відповідно лівосторонню або правосторонню вставку в не пусте дерево: insert(NewItem, tree(Element,Left,Right), tree(Element,NewLeft,Right):- NewItem < Element, !, insert (NewItem, Left, NewLeft). insert(NewItem, tree(Element,Left,Right), tree(Element, Left, NewRight)):- insert(NewItem, Right, NewRight). 7.5. Сортування по дереву. Якщо бінарне дерево пошуку вже побудоване, дуже просто розмістити всі його елементи в лексико-графічному порядку. Рекурсивний алгоритм буде включати зворотній обхід дерева: 1. Якщо дерево пусте, тоді нічого не потрібно робити. 2. В іншому випадку , переглянути всі елементи лівого піддерева, потім поточний елемент, потім всі елементи правого піддерева. Або ж в Пролозі: retrieve_all(empty). retrieve_all(tree(Item,Left,Right)):- retrieve_all(Left), do_something_to(Item), retrieve_all(Right). Таким чином, використовуючи сортування по дереву, ви можете швидко впорядковувати елементи. Таке впорядкування одне з найкращих. Так, для N елементів, часова оцінка роботи алгоритму буде О(N logN). 7.5. Програмна реалізація лексикографічного впорядкування при символьному вхідному потоці. В цій програмі ми будемо використовувати вмонтовані предикати Прологу для реалізації введення з клавіатури. Так, предикат READINT вводить цілі, а предикат READCHAR вводить символи. Стандартний предикат EXIT зупиняє процес виконання. domains chartree = tree(char, chartree, chartree). end predicates do(chartree) action(integer, chartree, chartree) create_tree(chartree, chartree) insert(char, chartree, chartree) write_tree(chartree) repeat goal do(end). clauses do(Tree):- makewindow(1,7,7,|character tree sort|,0, 0, 20, 60), repeat, clearwindow, write(|Enter 1 to create a tree |), write(|Enter 2 to show tree |), write(|Enter 7 to exit |), readint(X), action(X, Tree, NewTree), do(NewTree). action(1, Tree, NewTree):- write(|Enter characters or # toend: |), create_Tree(Tree, NewTree). action(2, Tree, Tree):- write_Tree(Tree), write(| Press a key to continue|), readchar(_). action(7, _, end):- exit. create_Tree(Tree, NewTree):- readchar(C), C <> 0.#. , !, write(C, | |), insert(C, Tree, TempTree), create_Tree(TempTree,NewTree). create_Tree(Tree, Tree). insert(New, end, tree(New, end, end)):- !. insert(New, tree(Element, Left, Right), tree(Element, NewLeft, Right)):- New < Element, !, insert(New, Left, NewLeft). insert(New, tree(Element, Left, Right), tree(Element, Left, NewRight)):- insert(New, Right, NewRight). write_Tree(end). write_Tree(tree(Item, Left, Right)):- write_Tree(Left), write(Item, | |), write_Tree(Right). repeat. repeat:-repeat. 7.1.Написати програму, яка б визначала кількість вершин-листків в бінарному дереві. 7.2.Написати програму, яка створює копію бінарного дерева. 7.3.Написати програму, яка знаходила б висоту бінарного дерева. Висота бінарного дерева Т визначається так: а)висота пустого дерева Т рівна H(T)=0. б)висота непустого бінарного дерева Т з коренем к і піддеревами Т1 і Т2 дорівнює H(T)=1+max(H(T1), H(T2)). 7.4.Написати програму, яка визначає кількість вузлів в бінарному дереві. 8. РОБОТА З СПИСКАМИ В ПРОЛОЗІ. Списки - це об.єкти, які можуть зберігати довільне число однотипних елементів. Наприклад: [1,2,3], [dog, cut, canary] Як ми вже зазначали, списки описуються за допомогою спеціального знаку (*) «зірочка». Він добавляється до кінця попередньо визначеної області. Наприклад, domains integerlist = integer* Eлemeнтом списку можуть бути любі дані, навіть інші списки. Всі елементи списку повинні належати до однієї області. Декларація областей для елементів повинна мати таку форму: domains elementlist = elements* elements = integer Складні списки є списками, які містять елементи різного типу. Враховуючи, що Пролог вимагає щоб всі елементи в списку належали одній області, ми повинні для створення складного списку використовувати функтори. Область може містити більш ніж один тип даних в якості аргументів до функторів. Наприклад: domains elementlist = elements* elements = i(integer). r(real). s(symbol) 8.1.Рекурсивна сутність списку. Список - це рекурсивна структура, яка складається з голови та хвоста. Головою називають перший елемент списку, а хвіст - це всі інші елементи. Хвіст списку завжди буде списком, а голова - один елемент. Зазначимо, що пустий список не можна розбити на голову і хвіст. Концептуально списки мають структуру дерева. Наприклад, список [a, b, c, d] можна представити в наступному вигляді: list / a list / b list / c list / d [] А одноелементний список, [a] має вигляд: list / a [] 8.2.Обробка списків. Пролог дає можливість явно створювати голову і хвіст списку. Замість відокремлення елементів комами, ви можете розділити голову і хвіст знаком (|). Наприклад, список [a, b, c] дорівнює списку [a | [b, c]] , який в свою чергу рівний списку [a|[b|[c|[]]]]. Розподільниками можна також комбінувати. Так список [a, b, c, d] можна задати у вигляді [a, b|[c, d]]. Для обробки списків найбільш підходять рекурсивні алгоритми. Обробка списку складається з рекурсивного зсуву і обробки голови списку до тих пір, поки список не стане пустим. Алгоритм такого типу, традиційно має дві фрази. Перша з них говорить, що потрібно робити з списком, а друга - що робити з пустим списком. 8.2.1.Друк списків. Список можна роздрукувати так: domains list = integer* /* або ж інший тип, який ви бажаєте використовувати */ predicates write_a_list(list) clauses write_a_list([]). /* якщо список пустий, тоді нічого не потрібно робити write_a_list([H|T]) :- /* Виділяємо голову списку Н і хвіст Т, потім роздруковуєм Н і рекурсивно обробляємо Т */ write(H), nl, write_a_list(T). Якщо ми задамо запит типу: goal : write_a_list([1, 2, 3]). Тоді список [1,2,3] буде розбито на голову Н=1 і хвіст Т = [2,3]. Предикатом write(H) роздрукується голова і рекурсивно буде оброблятись предикатом write_a_list(T) хвіст [2,3]. Процес закінчиться, коли хвіст стане пустим. 8.2.2.Підрахунок кількості елементів. Зараз ми розглянемо як можна визначити кількість елементів у списку, іншими словами, підрахуємо довжину списку. Можна дати наступне рекурсивне визначення довжини списку : Довжина пустого списку [ ] рівна 0. Довжина непустого списку рівна 1 плюс довжина його хвосту. В Пролозі цей алгоритм можна реалізувати за допомогою двох фраз: domains list = integer* predicates length_of(list, integer) clauses length_of([], 0). length_of([_|T], L) :- length_of(T, TailLength), L = TailLength + 1. Поглянемо спочатку на другу фразу. Так, length_of [_ ,|T] порівнює любий непустий список, прив.язуючи T до хвосту списка. Значення голови не суттєво, ЕОМ буде її рахувати як один елемент. Так ціль goal: length_of([1,2,3], L) , використовуючи другу фразу, зв.яже з T значення [2,3]. Наступний крок - обчислити довжину T. Коли це зроблено, не важливо як, тоді TailLength отримає значення 2, і ЭВМ потім зможе добавити до неї 1 та прив.язати L до 3. Для того, щоб визначити довжину [2,3] рекурсивно викличеться length_of([2,3], TailLength. Ця ціль зрівнює другу фразу, прив.язуючи - [3] до T . Тепер виникає задача, як знайти довжину [3], яка дорівнює 1, а потім добавить 1, щоб отримати довжину [2,3], яка буде 2. І так далі і тому подібно. Тому length_of знов викличе себе рекурсивно, щоб отримати довжину списку [3]. Хвіст для [3] рівний [ ], тому T зв.яжеться з [], і задача зараз полягає в тому , щоб знайти довжину [], потім додати до неї 1, і знайти довжину [3]. На цей раз це зробити легко. Ціль length_of([], Tail Length зрівнюючи першу фразу, зв.яже TailLength з 0. Тепер ЭОМ може додати 1 до неї, отримуючи довжину списку [3] і повернутися до фрази виклику. Яка , в свою чергу , прибавить знову 1 , отримуючи довжину [2,3] і повернеться до фрази, яка викликала її. ця початкова фраза прибавить знову 1 , знаходячи довжину списку [1,2,3]. Малюнок 8.1 показує дійсний процес обчислення довжини списку. Ми використали тут різні змінні, щоб підкреслити той факт, що змінні з одинаковими іменами в різних фразах , або різних викликах однієї і тієї ж фрази, будуть різними. length-of([1,2,3],L1) length-of([2,3],L2) length-of([3],L3) length-of([],0) L3 = 0 + 1 = 1 L2 = L3+ 1 = 2 L1 = L2+ 1 = 3 Мал.8.1.Обчислення довжини списку. 8.2.3.Іще один варіант підрахунку довжини списку. Як ви бачите, предикат length_of не є хвостовою рекурсією. Чи можливо створити рекурсивно-хвостовий предикат визначення довжини списку? Можливо, але для цього потрібно прикласти певні зусилля. Проблема з length_ of заключається в тому, що ми не можемо обчислити довжину списку, пока не підрахуємо довжину хвоста. Та все ж така можливість мається. Використаємо предикат з трьома аргументами. - Перший є список, котрий ЕОМ буде читати при кожному виклику, поки він не стане пустим. - Другий є вільним аргументом, який в кінці роботи буде визначати результат. - Третій є лічильником, котрий починається з 0 і збільшується з кожним викликом. В кінці лічильник можна уніфікувати з незв.язаним результатом. Наступна програма реалізує наш підхід. domains list = integer* predicates length_of(list, integer, integer) clauses /* * * * * * * * * * * * * * * * * * * * * * * * Якщо список пустий, тоді уніфікувати другий * * результуючий аргумент предикату з третім * * аргументом - лічильником * * * * * * * * * * * * * * * * * * * * * * * */ length_of([], Result, Result). /* * * * * * * * * * * * * * * * * * * * * * * * * * * * В іншому випадку, додати 1 до лічильника і рекурсивно * * зв.язати результат цього кроку з результатом в майбутньому. * * * * * * * * * * * * * * * * * * * * * * * * * * * */ length_of([_|T], Result, Counter):- NewCounter=Counter + 1, length_of(T, Result, NewCounter). Запит до цієї програми повинен також мати вмонтований предикат друку. Наприклад: goal : length_of([1,2,3], L, 0), /* починає з значенням Counter = 0 */ write(L), nl. Остання версія програми length_of більш складна і менш логічна. 8.2.4.Модифікація списку. Модифікація списку заключається в якійсь зміні уже існуючого списку. Традиційно, така зміна проводиться послідовною обробкою елементів списку. Прикладом модифікації списку може служити програма, яка додає до кожного елементу списку 1. Обчислення, які повинна виконувати програма, можна описати наступним чином: 1.Зв.язати голову і хвіст початкового списку відповідно з Head і Tail. 2.Зв.язати голову і хвіст результату з Head1 і Tail1 (Head1 і Tail1 ще не мають значень). 3.Додаючи 1 до Head, отримаємо Head1. 4.Рекурсивно додайте 1 до всіх элементів Tail, отримаєте Tail1. Наступна програма реалізує запропонований алгоритм. domains list = integer* predicates add1(list, list) clauses add1([], []). add1([Head|Tail], [Head1|Tail1]) :- Head1= Head+1, add1(Tail,Tail1). Розглянемо ще одну програму модифікації списку. Вона сканує вхідний список і переписує його без від.ємних чисел. domains list = integer* predicates discard_negatives(list, list) clauses discard_negatives([], []). discard_negatives([H|T], ProcessedTail) :- /* якщо Н є від.ємним, тоді пропустити його */ H < 0, !, discard_negatives(T, ProcessedTail). discard_negatives([H|T], [H|ProcessedTail]) :- discard_negatives(T, ProcessedTail). Наступний предикат копіює елементи списку, повторюючи їх два рази. doubletail([],[]). dou bletail([H|T],[H|H| doubletail ]) : - doubletail(T, doubletail ). 8.2.5.Належність елемента списку. Припустимо, ми маємо список імен. Нам потрібно написати предикат, який би встановлював належність якогось імені (перший аргумент) вибраному списку імен (другий аргумент ). Нехай цим предикатом буде предикат: member(name, namelist) В наступній програмі перша фраза досліджує голову списку. Якщо голова списку співпадає з іменем, яке ми шукаємо , тоді можна зробити заключення, що ім.я належить списку. Тому, що в даному випадку хвіст списку нас не цікавить, він характеризується анонімною змінною. Якщо ж імені немає в голові, тоді його потрібно рекурсивним чином шукати в хвості списку. За це і відповідає друга фраза програми. domains namelist = name* name = symbol predicates is_a_member_of(name, namelist) clauses is_a_member_of(Name,[Name|_]). is_a_member_of(Name,[_|Tail]):- is_a_member_of(Name,Tail). 8.3.Використання одного й того ж предикату для вирішення різних задач. Особливість ПРОЛОГУ заключається в тому, що коли ви будуєте предикат для вирішення якоїсь конкретної задачі , то він може використовуватись і для вирішення зовсім інших задач. Продемонструємо це на наступному прикладі. Побудуємо предикат конкатенації двох списків з трьома аргументами: append(List1,List2,List3) де List3 є результуючим списком. Використаємо наступний рекурсивний алгоритм. Якщо перший список пустий, тоді результуючий список буде рівний другому списку (append([],List2,List2)). Інакше, головою третього списку становиться голова першого списку, а хвостом - залишок першого списку і другий список. Прийдемо до програми: domains integerlist = integer* predicates append(integerlist, integerlist, integerlist) clauses append([], List, List). append([X|L1], List2, [X|L3]) :- append(L1, List2, L3). Якщо ми задамо ціль goal: append([1,2],[3,4]), тоді отримаємо список [1,2,3,4]. З іншого боку, розглядаючи предикат append з декларативної точки зору, ми визначили відношення між трьома списками. Таке відношення буде вірним і у випадку, коли буде відомий тільки третій список. Наприклад, goal: append(L1,L2,[1,2,4] дасть результат L1 = [], L2 = [1,2,[1,2,4] l1 = [1], l2 = [2,4] . . . Також ви можете використати предикат append, щоб визначити який із списків можна додати до списку [3,4], щоб отримати список [1,2,3,4]. Наприклад, задавши goal: append[L1,[3,4],[1,2,3,4] матимемо L1 =[1,2] Предикат append визначає відношення між множинами на вході і виході. Тому відношення може використовуватись різними способами. Задаючи таке відношення, ви можете запитати: Який вихід відповідає даному входу? або ж Який вхід відповідає даному виходу? Статус аргументів даного предикату при виклику, базується на зразку потоку даних. Предикат append може обробляти любий зразок потоку даних. Але не всі предикати Прологу можуть бути викликані різними зразками потоку даних. Якщо фраза Прологу може оброблятись різними зразками потоку даних, тоді її називають інвертованою фразою. Зазначимо, що використання інвертованих фраз додає потужності вашим предикатам. 8.4. Знаходження зразу всіх розв.язків. Як ми вже зазначали раніше, для задання ітераційних процесів в Пролозі, використовується бектрекінг, або ж рекурсія. Рекурсія - більш потужніший засіб. Вона, використовуючи апарат формальних аргументів, може передавати інформацію від одного виклику до іншого. Іншими словами, рекурсія дозволяє відсліджувати часткові результати, аналізувати лічильники. Але іноді виникає проблема, яку важко вирішити і за допомогою рекурсії. Нехай вам потрібно знайти зразу всі розв.язки задоволення цілі, як частини єдиної складної структури даних. Пролог вирішує дану проблему за допомогою предикату findall, який приймає ціль як один із своїх аргументів, збираючи всі розв.язки цієї цілі в один список. Предикат findall має три аргументи: - Перший аргумент VarName визначає який з аргументів в зазначеному предикаті потрібно відібрати в список. - Другий, Мypredicate, визначає предикат, з якого будуть збиратись значення. - Третій аргумент, ListParam, з змінною, якою позначається список значень, зібраних через перебір з поверненнями. Зазначимо, що попередньо повинна бути визначена область, до якої повинні належати значення ListParam. Наступна програма використовує findall, для визначення середнього віку групи людей. domains name, address = string age = integer list = age* predicates person(name, address, age) sumlist(list, age, integer) goal findall(Age, person(_, _, Age), L), sumlist(L, Sum, N), Ave = Sum/N, write(|Average =|, Ave), nl. clauses sumlist([], 0, 0). sumlist([H|T], Sum, N) :- sumlist(T, S1, N1), Sum=H+S1, N=1+N1. person(|Sherlock Holmes|, |22B Baker Street|, 42). person(|Pete Spiers|, |Apt. 22, 21st Street|, 36). person(|Mary Darrow|, |Suite 2, Omega Home|, 51). В цій програмі фраза findall створює список L, який містить числа, які відповідають віку всіх людей з предикату person. Якщо ви бажаєте зробити список людей вік яких 42 роки, тоді ви можете написати ціль findall(Who, person(Who,_,42), List). 8.5.Складні списки. Часто вам потрібно зберігати комбинацію різних типів елементів всередині одного списку, як наприклад [2,3,5,12,[food,|goo|], |new|] Складними будемо називати списки, які містять більше одного типу аргументів. Нам будуть потрібні спеціальні декларації, щоб обробити списки багатотипних елементів, тому що Пролог вимагає, щоб всі елементи списку належали одній області. Для опису різнотипних списків потрібно використовувати функтори. Наступний приклад декларації області для списку, який може мати символ, ціле число, літеру, стрічку або ж список із них. Декларація списку повинна мати функтор, а потім повинна бути декларована рекурсивно. Так, попередній список повинен бути описаний: domains llist = l(list). s(symbol). i(integer). c(char). t(string) list = llist * І буде задаватись в Пролозі: [i(2),і(3),i(5),i(12), [c(food),s(«goo»)],s(«new»)] Наступний приклад з предикатом append показує як використовувати такий опис: domains llist = l(list). s(symbol). i(integer). c(char). t(string) list = llist * predicates append(list, list, list) goal makewindow(1,7,7, |answer|,15,0,8,80), /*Note how you can use the same code but need functors * * append([likes,[bill,mary]],[bill,sue],Ans) */ append([s(likes),l([s(bill),s(mary)])],[s(bill),s(sue)],Ans), */ write(|First List:|, Ans), nl,nl, /*The trick is to write the list first, than add the functors * * append([apple,[[[47], .1.]], [[[|This is a string|,b,7, * * .w.]],bee], [.c.], Ans2) */ * append([l[s(|This|), s(|is|,s(|a|),s(|list|))]), s(bee)], [c(.c.)], Ans2), write(|Second List :|, Ans2), nl. clauses /* Concatenate two lists */ append([], L, L). append([X|L1], L2, [X|L3]) :- append(L1, L2, L3). 8.6.Реалізація синтаксичного аналізу за допомогою списків. Розглянемо задачу синтаксичного аналізу для деякої примітивної мови програмування паскалеподібного типу. Розіб.ємо задачу на дві підзадачі: сканування і синтаксичний аналіз. Розглянемо програму: domains toklist = string* predicates tokl(string, toklist) clauses tokl(Str, [H | T]):-fronttoken(Str,H,Str1),!, tokl(Str1,T). tokl(_,[]). /* Друга частина програми є синтаксичним аналізатором */ domains program = program(statementlist) statementlist = statement* /* визначення типу оператора */ statement = if_Then_Else(exp,statement, statement). if_Then(exp,statement). while(exp,statement). assign(id,exp) /* визначення виразу */ exp = plus(exp,exp). mines(exp,exp). var(id). int(integer) id = string predicates s_program(toklist, program) s_statement(toklist, toklist, statment) s_statementlist(toklist, toklist, statmentlist) s_exp(toklist, toklist, exp) s_exp1(toklist, toklist, exp, exp) s_exp2(toklist, toklist, exp) clauses s_program(List1, program(Statementlist)):- s_statementlist(List1, List2, Statementlist), List2 = []. s_statementlist([], [],[]):-!. s_statementlist([List1, List4, [Statement | Program]):- s_statement(List1, List2, Statement), List2 = [|.| | List3], s_statementlist(List3, List4, Program). s_statement([|if| | List1], List7, if_theh_else(Exp,Statement1, Statement2)):- s_exp(List1,List2, Exp), List2 = [ |then| | List3], s_statement(List3, List4, Statement1), List4 = [|else| | List5],!, s_statement(List5, List6, Statement2), List6 = [|fi| | List7]. s_statement([| if..... . . . s_statement([ | do ..... . . . s_statement([Id | List1], List3, assign(Id,Exp)):- isname(Id), List1 = [|=| | List2], s_exp(List2,List3,Exp). s_exp(List1,List3,Exp):- s_exp2(List1,List2,Exp1), s_exp1(List2,List3,Exp1,Exp). s_exp1([|+| | List1],List3,Exp1,Exp):-!, s_exp2(List1,List2,Exp2), s_exp1(List2,List3,plus(Exp1,Exp2), Exp). s_exp1([|-| ........ s_exp1(List,List,Exp,Exp). s_exp2([Int | Rest],Rest, int(I)):-str_int(Int,I),!. s_exp2([Id | Rest],Rest,var(Id)):-isname(Id). Предикат tokl є сканером. він аналізує стрічку і перетворює її в список лексем. Всі предикати, які починаються з s є предикатами синтаксичного анализу. В цьому прикладі вхідний текст є программою на псевдопаскалі. Вона включає оператори: IF THEN ELSE, IF THEN, DO WHILE і ASSIGNMENT. Для побудови виразів використовуються дії додавання і віднімання над змінними і константами цілого типу. Програма працює наступним чином: 1.Перша фраза сканера, s_program, приймає список лексем і перевіряє чи може він бути трансформований в список тверджень. 2.Предикат s_statement приймає той же список лексем і перевіряє чи зможуть лексеми бути разділені на індивідуальні твердження, кожне з яких закінчується крапкою з комою. 3.Предикат s_statement перевіряє чи будуть перші лексеми з списку лексем допустимими твердженнями. Якщо так, тоді твердження повертається в структуру, а ті лексеми, що залишились повертаються в s_statement. а)Чотири фрази s_statement відповідають чотирьом типам операторів псевдопаскалю. Вони аналізуються послідовно. б)Потім проводиться порівняння з виразами. 4.Предикати sexp, s_exp1 і s_exp2 працюють аналогічно з s_statment, але тільки по відношенню до виразів. Якщо системі побудувати запит: goal: tokl(|b=2. if b then a=1 else a=2 fi. do a=a-1 while a . |, Ans), s_program(Ans,Res) тоді вона побудує відповідь: Ans = [|b|, |=|,...] Res = program([assign(|b|, int(2)), if_then_else(var(|b|), assign(|a|,int(1))........]) 8.1.Визначте два предикати парнадовжина (Список) і непарнадовжина (Список), таким чином, щоб вони були істинними, якщо їх аргументом є список парної або непарної довжини відповідно. 8.2.Визначте предикат паліндром (Список). Список називається паліндромом, якщо він читається однаково, як зправа наліво, так і зліва направо. Наприклад [м,а,д,а,м]. 8.3.Визначте відношення переклад(Список1, Список2) для модифікації списка чисел від 0 до 9 в список відповідних слів. Наприклад, переклад ([3,1,7],[три,один,сім]) 8.4.Визначте відношення лінеризація (Список1, ЛінійнийСписок), де ЛінійнийСписок - це той же список, але «вирівняний» таким чином, що елементи його підсписків складають один лінійний список. Наприклад: goal: лінеризація ([a,d,[c,d],[],[[[e]]],f],L). L=[a,b,c,d,e,f]. 9. ТЕХНІКА ПРОГРАМУВАННЯ В ПРОЛОЗІ. В цьому розділі ми розглянемо базові підходи до реалізації основних типів алгоритмів в Пролозі. 9.1.Принципи побудови експертної системи. Розглянемо наступну задачу. Потрібно реалізувати експертну систему, яка б визначала тварину, яку мав на увазі користувач із семи зазначених. Експертна система знайде тварину за допомогою опитування користувача. Цей приклад демонструє бектрекінг для перегляду бази даних і показує ефективне використання предикату not. Типовим діалогом користувача з експертною системою може бути наступний: goal: run. Has it hair? yes does it eat meat? yes has it a fawn color? yes has it dark spots? yes Your animal may be a (an) cheetah! Для програмування діалогу потрібні два кроки. Перший крок заключається в наповненні бази системи знаннями, а результуючий - в побудові виведення відповіді. Повна програма приведена на малюнку 9.1. database xpositive(symbol, symbol) xnegative(symbol, symbol) predicates animal_is(symbol) it_is(symbol) ask(symbol, symbol, symbol) remember(symbol, symbol, symbol) positive(symbol, symbol) negative(symbol, symbol) clear_facts run clauses animal_is(cheetah) :- it_is(mammal), it_is(carnivore), positive(has, tawny_color), positive(has, dark_spots). animal_is(tiger) :- it_is(mammal), it_is(carnivore), positive(has, tawny_color), positive(has, black_stripes). animal_is(giraffe) :- it_is(ungulate), positive(has, long_neck), positive(has, long_legs), positive(has, dark_spots). animal_is(zebra) :- it_is(ungulate), positive(has,black_stripes). animal_is(ostrich) :- it_is(bird), negative(does, fly), positive(has, long_neck), positive(has, long_legs), positive(has, black_and_white_color). animal_is(penguin) :- it_is(bird), negative(does, fly), positive(does, swim), positive(has, black_and_white_color). animal_is(albatross) :- it_is(bird), positive(does, fly_well). it_is(mammal) :- positive(has, hair). it_is(mammal) :- positive(does, give_milk). it_is(bird) :- positive(has, feathers). it_is(bird) :- positive(does, fly), positive(does,lay_eggs). it_is(carnivore) :- positive(does, eat_meat). it_is(carnivore) :- positive(has, pointed_teeth), positive(has, claws), positive(has, forward_eyes). it_is(ungulate) :- it_is(mammal), positive(has, hooves). it_is(ungulate) :- it_is(mammal), positive(does, chew_cud). positive(X, Y) :- xpositive(X, Y), !. positive(X, Y) :- not(xnegative(X, Y)), ask(X, Y, yes). negative(X, Y) :- xnegative(X, Y), !. negative(X, Y) :- not(xpositive(X, Y)), ask(X, Y, no). ask(X, Y, yes) :- !, write(X, | it |, Y, . .), readln(Reply), frontchar(Reply, .y., _), remember(X, Y, yes). ask(X, Y, no) :- !, write(X, | it |, Y, . .), readln(Reply), frontchar(Reply, .n., _), remember(X, Y, no). remember(X, Y, yes) :- assertz(xpositive(X,Y)). remember(X, Y, no) :- assertz(xnegative(X,Y)). clear_facts :- write(| Please press the space bar to exit |), retractall(_, dbasedom), readchar(_). run :- animal_is(X), !, write(| Your animal may be a (an) |,X), nl, nl, clear_facts. run :- write(| Unable to determine what|), write(|your animal is. |), clear_facts. Кожна тварина описується деяким числом характерних атрибутів, які вона має або ж не має. Вони задаються в предикатах animal_is і it_is. Питання, на які користувачу потрібно відповісти, реалізуються за допомогою використання предикатів рositive (X,Y) і negative (X,Y). Але система, між іншим, може задати і питання типу : Does it have hair? Отримавши відповідь, система приєднує її до попередньої інформації для подальшого використання. Для простоти цей приклад програми буде розглядати тільки стверджувальні та заперечувальні відповіді. Тому вона використовує базу даних, яка містить тільки два предикати: database xpositive(symbol,symbol) xnegative(symbol,symbol) Наприклад, твердження , що тварина не має волосся тоді може бути задане таким чином: xnegative(has,hair). Але, попередньо, перед тим , як задавати запитання, система перевіряє чи відповідь не була відома раніше: positive(X,Y):- xpositive(X,Y),!. positive(X,Y):- not (xnegative(X,Y)), ask(X,Y,yes). negative(X,Y):- xnegative(X,Y),!. negative(X,Y):- not (xpositive(X,Y)), ask(X,Y,no). Відмітимо, що останні правила, які використовуються тут при визначенні предикатів positive і negative забезпечують реалізацію тієї ситуації, щоб спростування не трапилось раніше, ніж пройшло опитування користувача. Предикат ask задає питання і організовує обробку відповіді. Якщо відповідь починається з букви Y, тоді система приймає відповідь Yes, а, якщо відповідь починається з N, тоді в якості відповіді приймається - No. ask(X,Y,yes):- !, write(X,|it|,Y,. .), readln(Reply), frontchar(Reply, .y.,_), remember(X,Y,yes). ask(X,Y,no):- !, write(X,|it|,Y,. .), readln(Reply), frontchar(Reply, .n.,_), remember(X,Y,no). remember(X,Y,yes):- assertr(xpositive(X,Y)). remember(X,Y,no) :- assertr(xnegative(X,Y)). При роботі з базами даних потрібно також пам.ятати наступне. Під час поповнення бази новими фактами, старі факти повинні зсуватись, щоб не затертись новими. Цю функцію в програмі виконує вмонтований предикат retractall, який використовується при визначенні предикату clearfacts. clear_facts:- write(| Please press the space bar to exit |), retractall(_, dbasedom), readchar(_). Якщо ви попередньо наберете програму і наповните базу, тоді для запуску програми ви можете використати предикат run. run:- animal_is(X),!, write(| Your animal may be a(an)|, X), nl,nl, clear_facts. run:- write(| Unable to determine what|), write(|your animal is. |), clear_facts. 9.2. Макетування: задача маршрутизації. Ця програма ілюструє особливості Прологу, які роблять його корисним при вирішенні задач макетування. Припустимо , ми хочемо створити систему, яка б допомогала вибрати маршрут при поїздці із одного міста в інше. Початкову програму будемо використовувати для подальшого аналізу вирішення поставленої задачі. Нас будуть цікавити питання типу: * Чи існує пряма дорога з одного міста в інше? * Які з міст знаходяться на віддалі меншій 10 км від конкретного міста? Нехай ми будемо реалізовувати карту прототипу, зображену на мал.9.2. KansasCity O--------------- Gordon O--------- O Houston --------O Tampa Мал.9.2. Карта прототипу. Наступна програма є класичним прикладом використання бектрекінгу і рекурсії для вирішення задачі планування маршруту. domains town = symbol distance = integer predicates road(town, town, distance) route(town, town, distance) clauses road(tampa, houston, 200). road(gordon, tampa, 300). road(houston, gordon, 100). road(houston, kansas_city, 120). road(gordon, kansas_city, 130). route(Town1, Town2, Distance) :- road(Town1, Town2, Distance). route(Town1, Town2, Distance) :- road(Town1, X, Dist1), route(X, Town2, Dist2), Distance=Dist1+Dist2, !. Кожна фраза для предикату road є фактом, який описує дорогу із одного міста в інше, довжина якої визначається в кілометрах. Фрази route характеризують те, чи можна створити маршрут із одного міста в інше через декілька проміжних пунктів. Третій параметр визначає пройдену відстань між містами. Предикат route визначається рекурсивно. маршрут може просто складатись із одного проміжку дороги ( перша фраза). В цьому випадку віддаль буде довжиною дороги. Ми також можемо сконструювати маршрут із Town1 в Town2, використовуючи проміжний пункт Х. Загальна віддаль буде тоді сумою віддалей між Town1 і Х а також із Х в Town 2, що й показано в другій фразі route. При подальшому аналізі задачі на складнішій структурі міст приходимо до необхідності вирішення наступних проблем: 1.Пролог система не повинна вибирати маршрут, який приводить до відвідин одного міста двічі. 2.Попередження переміщень по колу, яке дасть впевненість в тому, що програма не прийде до нескінченного циклу. Ці проблеми досить просто можна вирішити, якщо ми в програмі створимо і будемо заповнювати, а потім аналізувати список міст, які вже були відвідані при прокладенні маршруту. Приклад реалізації такого списку приводиться далі. 9.3.Пригоди в дивних печерах. Розв.яжемо модифіковану задачу пошуку шляху в лабіринті. Нехай ми маємо печеру з скарбами. Печера є лабіринтом галлерей, які з.єднують кімнати з монстрами та грабіжниками. В одній з кімнат знаходяться скарби. Будемо вважати, що вам треба зайти в печеру, забрать скарби і вийти живим з лабіринту. Розглянемо наступну карту печери: Мал. 20.2. Лабіринт галлерей. domains room = symbol roomlist = room* predicates gallery(room, room) /* існує коридор */ /* між двома кімнатами */ neighborroom(room, room) /* Визначення */ /* сусідських */ /* кімнат */ avoid(roomlist) go(room, room) route(room, room, roomlist) /* Тут roomlist */ /* містить кімнати */ /* відвідані */ member(room, roomlist) clauses gallery(entry, monsters). gallery(entry,fountain). gallery(fountain, hell). gallery(fountain, food). gallery(exit, gold_treasure). gallery(fountain, mermaid). gallery(robbers, gold_treasure). gallery(fountain, robbers). gallery(food, gold_treasure). gallery(mermaid, exit). gallery(monsters, gold_treasure). gallery(gold_treasure,exit). neighborroom(X, Y) :- gallery(X, Y). neighborroom(X, Y) :- gallery(Y, X). avoid([monsters, robbers]). go(Here, There) :- route(Here, There, [Here]). go(_, _). route(Room, Room, VisitedRooms) :- member(gold_treasure, 6 0VisitedRooms), write(VisitedRooms), nl. route(Room, Way_out, VisitedRooms):- neighborroom(Room, Nextroom), avoid(DangerousRooms), not(member(NextRoom, DangerousRooms)), not(member(NextRoom, VisitedRooms)), route(NextRoom, Way_out, [NextRoom|VisitedRooms]). member(X, [X|_]). member(X, [_|H]) :- member (X, H). Кожна печера описана фактом. Предикати go і route задають правила. Задавши програмі ціль go(entry,exit), отримаємо відповідь. Вона буде містити список кімнат, які ми повинні пройти, щоб забрати скарби і повернутись. Як ми і говорили, в попередньому розділі для усунення вад минулої програми використовується список уже пройдених кімнат. Ця дія виконується в рекурсивному предикаті route третім аргументом. Тому, якщо ви знаходитесь в кімнаті виходу, і цей список містить кімнату gold_treasure , тоді ви досягли поставленої мети. Звернемо вашу увагу на наступне. Враховуючи нашу побудову предикату route, якщо задача може мати і декілька розв.язків, програма буде завжди видавати тільки один розв.язок. Для видачі всіх можливих розв.язків нам потрібно організувати бектрекінг за допомогою предикату fail в першому правилі визначення route: route(Room,Room,VisitedRooms):- member(gold_treasure, VisitedRooms), write(VisitedRooms), nl, fail. 9.4. Моделювання апаратних засобів. Прологівські програми є зручними для моделювання роботи різних складних систем обробки інформації, наприклад радіотехнічних систем. Кожна логічна лінія зв.язку може бути описана відповідним предикатом прологу. Предикат характеризує відношення між сигналами на вході і виході. Базові функції основних компонент об.єктів описують за допомогою таблиць істинності. Покажемо як це робиться на прикладі моделювання роботи лінії зв.язку типу взаємовиключного АБО, схема якого приведена на малюнку 9.3. Мал .9.3. Базова лінія зв.язку XOR. В наступній програмі вона описана предикатом xor. domains d = integer predicates not_(d, d) and_(d, d, d) or_(d, d, d) xor(d, d, d) clauses not_(1, 0). not_(0, 1). and_(0, 0, 0). and_(0, 1, 0). and_(1, 0, 0). and_(1, 1, 1). or_(0, 0, 0). or_(0, 1, 1). or_(1, 0, 1). or_(1, 1, 1). xor(Input1, Input2, Output) :- not_(Input1, N1), not_(Input2, N2), and_(Input1, N2, N3), and_(Input2, N1, N4), or_(N3, N4, Output). Якщо ми задамо ціль : goal: xor(Input1,Input2,Output) Проінтерпретуємо отриманий результат як таблицю істинності, тоді ми можемо перевірити, чи наша програма вірно моделює потрібну лінію зв.язку. 9.5.Задача про ханойські башні. Розглянемо класичну задачу про ханойські башні. Історія цієї задачі базується на старовинній легенді про буддійський монастир у В.єтнамі. Легенда говорить про наступне. В цьому храмі монахи постійно, з давніх часів, виконують таку роботу. Вони переміщують по спеціальному алгоритму шістдесят чотири диски на трьох сердечниках при певних обмеженнях. Як тільки вони закінчать переміщення дисків з першого сердечника на третій, наступить кінець світу. Уточнимо постановку задачі. Нехай ми маємо три спеціальних сердечники, на яких проходить переміщення дисків. Висота сердечників достатня для того, щоб на ній могли розміститись всі n дисків. Всі диски різного діаметру, а внутрішній отвір більший за діаметр сердечників. Спочатку всі диски розміщені на першому сердечнику в спадному, згідно зовнішнього діаметра, порядку. Їх потрібно перенести на третій сердечник, використовуючи другий сердечник, так , щоб вони розмістились в такому ж порядку, як були на першому сердечнику. При переміщеннях потрібно дотримуватись такого обмеження: ніколи диск більшого диаметра не може знаходитись зверху хоча б над одним диском меншого діаметра. Для переносу можна запропонувати наступний рекурсивний алгоритм. * Один диск можна перенести прямо на потрібний сердечник. * N дисків можна перемістить так: 1.Перемістить останній (N-ий) диск прямо на третій (правий) сердечник. 2.Перемістить N-1 диск на другий (середній) сердечник. 3.Перемістить прямо N-ий диск з третього сердечника на перший (лівий). 4.Перемістить N-1 диск з другого на третій. 5.Перемістить N-ий диск прямо з першого на третій сердечник. Програма Прологу, яка вирішуз задачу про Ханойські Башні, буде використовувати три предикати: 1. hanoi з одним параметром, який характеризує загальну кількість дисків. 2. move, який описує переміщення N дисків з одного сердечника на інший, використовуючи третій сердечник, як тимчасове місцезнаходження дисків. 3. inform, відображає на екрані дисплею, як проходять переміщення. domains loc = right. middle. left predicates hanoi(integer) move(integer, loc, loc, loc) inform(loc, loc) clauses hanoi(N) :- move(N, left, middle, right). move(1, A, _, C) :- inform(A, C), !. move(N, A, B, C) :- N1=N-1, move(N1, A, C, B), inform(A, C), move(N1, B, A, C). inform(Loc1, Loc2) :- write(| Move a disk from |, Loc1, |to|, Loc2). Для вирішення задачі з трьома дисками, потрібно задати ціль goal: hanoi(3). 9.6.Ділення слів на склади. На прикладі вирішення цієї задачі продемонструємо можливості Прологу при обробці текстової інформації в редакторах. Для вирішення задачі ділення слів на склади, будемо використовувати простий алгоритм, який базується на впорядкуванні голосних і приголосних в слові. Наприклад, розглянемо дві послідовності: 1) приголосна - голосна - приголосна. В цьому випадку, слово ділится після першої голосної: ruler ---> ru-ler prolog ---> pro-log 2) голосна - приголосна - приголосна. В цьому випадку , слово ділиться між двома приголосними: number ---> num-ber panter ---> pan-ter Ці два правила добре застосовуються для більшості слів, але не працюють для слів типу handbook и hungry, які не підходять до жодного правила. Такі слова програма повинна обробляти спеціальним чином, наприклад використовувати бібліотеку таких слів. Напишимо програму. Вона повинна запрошувати ввести слово, яке потрібно розбити на склади. Для застосування нашого алгоритму нам спочатку потрібно розбити слово на символи. Тому нам необхідний наступний опис: domains letter = symbol word =letter* Нам потрібно мати предикат, який визначає тип букви: голосна чи приголосна. Для розпізнання голосних використаємо набір фактів типу: vocal(a), vocal(e),...,vocal(y). Приголосна визначається як буква, яка не є голосною: consonant(L):- not(vocal(L)). Нам також будуть потрібні ще два предикати. Перший, типу: append(word,word,word) і другий для перетворення стрічки символів в список символів: string_word(string,word) Цей предикат буде використовувати стандартний предикат frontchar, який має три параметри. Перший параметр з стрічкою, яка розбивається на дві частини: перший символ стрічки (визначається другим аргументом) і залишок стрічки (третій аргумент). Вмонтовані предикати free і bound визначають чи змінна є вільною чи зв.язною. Зараз ми вже готові до вирішення основної задачі: визначити предикат divide, який разділяє слово на склади. divide має чотири пареметри і носить рекурсивний характер. Перший і другий аргументи визначають початкове слово, а третій і четвертий параметри визначають уже розбите слово. Наприклад , перше правило для divide реалізується divide(Start,[T1,T2,T3 | Rest], D, [T2,T3 | Rest]):- vocal(T1), consonant(T2), vocal(T3), append(Start, [T1], D), де Start - це список першої групи символів слова, яке ми ділимо. Наступні три символи в слові задаються Т1,Т2 і Т3, тоді в Rest зберігаються символи, що залишились. Наприклад, при розбитті слова prolog, це правило задовольниться викликом: divide([p,r], [o,l,o,g], P1,P2) , який перетвориться в divide([p,r], [o,l,o, | [g]], [p,r,o], [l, o ,g ]) , тому що предикат append конкатенує першу голосну до кінця початкових літер слова. P1 становится прив.язаною до [p,r,o], а P2 прив.язана до [l,o,g]. Друге правило для divide реалізується в повній програмі: domains letter = char word = letter* predicates divide(word, word, word, word) vocal(letter) consonant(letter) string_word(string, word) append(word, word, word) repeat goal clearwindow, repeat, write(|Write a multi-syllable word: |), readln(S), string_word(S, Word), divide([], Word, Part1, Part2), string_word(Syllable1, Part1), string_word(Syllable2, Part2), write(|Division: |,Syllable1,|-|,Syllable2),nl, fail. clauses divide(Start, [T1, T2, T3|Rest], D1, [T2, T3|Rest]):- vocal(T1), consonant(T2), vocal(T3), append(Start, [T1], D1). divide(Start, [T1, T2, T3, T4|Rest], D1,[T3, T4|Rest]):- vocal(T1), consonant(T2), consonant(T3), vocal(T4), append(Start, [T1, T2], D1). divide(Start, [T1|Rest], D1, D2):- append(Start, [T1], S), divide(S, Rest, D1, D2). vocal(.a.).vocal(.e.).vocal(.i.). vocal(.o.).vocal(.u.).vocal(.y.). consonant(B):- not(vocal(B)), B <= .z., .a. <= B. string_word(||, []):-!. string_word(Str, [H|T]):- bound(Str), frontchar(Str, H, S), string_word(S, T). string_word(Str, [H|T]):- free(Str), bound(H), string_word(S, T), frontchar(Str,H,S). append([], L, L):-!. append([X|L1], L2, [X|L3]) :- append(L1, L2, L3). repeat. repeat :- repeat. 9.7. Задача про N королев. Задача про N королев формулюється наступним чином. Потрібно розставити на шахматній досці N королев таким чином , щоб ніякі дві королеви не змогли побити одна одну згідно правил гри в шахи. Тому, ніякі дві королеви не можуть бути розміщені в одному ряду: по вертикалі , горизонталі , діагоналі. Для вирішення задачі, пронумеруємо вертикальні та горизонтальні рядки шахматної доски від 1 до N. Для нумерації діагоналі , розділимо їх на два типи таким чином , щоб діагональ специфицифікувалась типом і номером, які обчислюються із її вертикальних і горизонтальних рядів: Diagonal = N + Column - Row (type 1) Diagonal = Row + Column - 1 (type 2) Якщо ви дивитесь на шахматну доску на ряд 1 по горизонталі та колонку 1 по вертикалі з лівої сторони , тоді Tun1 розділяє діагоналлю клітку як символ похилої риски вліво (), а Tun2 - вправо (/). Малюнок9.5. демонструє нумерацію діагоналей Tunу2 на досці 4х4. | 1 | 2 | 3 | 4 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 | 5 | 3 | 3 | 4 | 5 | 6 | 4 | 4 | 5 | 6 | 7 | Мал. 9.5. Нумерація діагоналей Типу2 на шахматній досці. Для вирішення задачі про N королев на Пролозі, ми повинні вміти встановлювати який рядок, колонка і діагональ ще не зайняті , а також вміти відмічати де вже розміщені королеви. Позицію королеви можна описати за допомогою зазначення номера рядка та колонки: queen = q(integer, integer) . Такий опис задає позицію одної королеви. Для фіксації більшої кількості позицій, можемо використать список: queens = queen* . Нам, також, будуть потрібні декілька списків чисел, які будуть визначати ще не зайняті королевами ряди , колонки та діагоналі. Ці списки опишемо наступним чином: freelist = integer* . Шахматну дошку зможемо обробляти як єдиний об.єкт, якщо зробимо наступний опис: board = board(queens, freelist,freelist,freelist,freelist) де чотири аргументи типу freelist задають відповідно ряди, колонки та діагоналі Типу1 і Типу2. Наприклад, шахматну доску 4х4 без королев можна задать: board([],[1,2,3,4],[1,2,3,4],[1,2,3,4,5,6,7],[1,2,3,4,5,6,7]), а шахматну доску з однією королевою в самому лівому верхньому кутку опише предикат: board([q(1,1)],[2,3,4],[2,3,4],[1,2,3,4,5,6,7],[2,3,4,5,6,7]) Накінець, ми можемо вирішити поставлену задачу, описуючи відношення між пустою доскою і доскою з N королевами. Визначимо предикат placeN(integer, board, board) з двома фразами. Королеви розташовуються одна за одною, поки кожний рядок і кожна колонка не будуть зайняті. Тому в першій фразі два списки freerows і freecols - пусті: placeN(_, board(D,[],[],X,Y), board(D,[],[],X,Y)):- !. placeN(_, Board1, Rеsult):- place_a_queen(N, Board1, Board2), place_N(N, Board2, Result). В другій фразі предикат place_a_guun описує зв.язок між Board1 і Board2. В Board2 на одну королеву більше, ніж в Board1. Для опису предикату можемо використати наступну декларацію: plase_a_queen(integer, board, board) Тому суть задачі з N королевами заключається в тому, щоб описати , як можна розмістити максимальну кількість королев на досці, починаючи з пустої доски. Реалізовувать таке поповнення королев будемо через поповнення списку новою королевою : [q(R,C) | Queens]. Для розміщення наступної королеви нам потрібно серед вільних рядів Rows знайти ряд R, в якому ми зможемо розмістити королеву. Потім видалимо R і з списку вільних рядів NewR. Цю роботу буде виконувати предикат: findandremove( R, Row, NewR) . Аналогічні дії ми повинні зробити і з вакантною колонкою С. Із R і C ми також можемо обчислити номера зайнятих діагоналей. А потім ми зможемо визначити чи є серед D1 і D2 вільні діагоналі. place_a_gueen( N, board(Queens,Rows,Columns,Dig1,Dig2), board([q(R,C) | Queens],NewR,NewS,NewD1,NewD2)):- findandremove( R, Rows, NewR), findandremove( C, Columns, NewC), D1 = N + S + R, findandremove(D1, Diag1, NewD1), D2 = R + S - 1, findandremove(D2, Diag2, NewD2). Далі ми приводимо повну програму, яка містить тільки декілька добавок. Ці добавки розраховані на те, щоб ви одним викликом: goal: nqueens(5), могли задати пошук рішення для розміщення п.яти королев на досці 5х5. domains queen = q(integer, integer) queens = queen* freelist = integer* board = board(queens, freelist, freelist, freelist, freelist) predicates placeN(integer, board, board) place_a_queen(integer, board, board) nqueens(integer) makelist(integer, freelist) findandremove(integer, freelist, freelist) nextrow(integer, freelist, freelist) clauses nqueens(N) :- makelist(N, L), Diagonal = N*2-1, makelist(Diagonal, LL), placeN(N, board([], L, L, LL, LL), Final), write(Final). placeN(_, board(D, [], [], D1, D2), board(D, [], [], D1, D2)):- !. placeN(N, Board1, Result) :- place_a_queen(N, Board1, Board2), placeN(N, Board2, Result). place_a_queen(N, board(Queens, Rows, Columns, Diag1, Diag2), board([q(R,C)|Queens], NewR, NewC, NewD1, NewD2)):- nextrow(R, Rows, NewR), findandremove(C, Columns, NewC), D1 = N+C-R, findandremove(D1, Diag1, NewD1), D2 = R+C-1, findandremove(D2, Diag2, NewD2). findandremove(X, [X|Rest], Rest). findandremove(X, [Y|Rest], [Y|Tail]):- findandremove(X, Rest, Tail). makelist(1, [1]). makelist(N, [N|Rest]) :- N1 = N-1, makelist(N1, Rest). nextrow(Row, [Row|Rest], Rest). Вправи. 9.1.Написати програму, яка моделює роботу недетермінованого скінченного автомату. 9.2.Напишіть програму, яка зливає два впорядковані списки в один впорядкований список. 9.3.Граф називається зв.язаним, якщо між довільними двома вершинами існує шлях. Нехай G=(V,E»), де E» така підмножина Е, що 1) Т - зв.язний граф 2) в Т не має циклів Написати предикат остдерево(G,T), де Т - остове дерево G. 9.4.Розглянемо наступну задачу планування. Маємо набір задач t1, t2, ..., які мають час виконання відповідно Т1, Т2, ... . Всі задачі потрібно обробити на m ідентичних процесорах. Кожна задача може бути вирішена на довільному процесорі, але в кожний даний момент часу кожний процесор вирішує тільки одну із задач. Між задачами існує відношення порядку, яке визначає, котрі з задач (якщо такі є), мають бути завершені, перш ніж дана задача може бути оброблена. Потрібно розподілити задачі між процесорами таким чином, щоб не порушити відношення порядку, причому так, щоб вся сукупність задач була вирішена за мінімальний час. 10.ОСОБЛИВІ ТЕХНІЧНІ ПРИЙОМИ ДЛЯ ПРОФЕСІОНАЛІВ. 10.1.Потоковий аналіз. Нагадаємо, що ми домовлялись вхідні (відомі) аргументи предикату позначати типом вводу (і) - input, а вихідні (невідомі) аргументи позначати типом (o) - output. Зразок вхідних і вихідних аргументів в предикаті будемо називати потоковим зразком (flow pattern). Наприклад, якщо предикат викликається з двома аргументами, тоді існує чотири можливості для потокового зразку: (i,i) (i,o) (o,i) (o,o) При компіляції програми, Пролог виконує глобальний потоковий аналіз предикатів. Він починається з основної цілі. Потім він виконує псевдорозвиток всієї програми, під час якого прив.язує потокові зразки до всіх предикатних викликів в програмі. Потоковий аналіз досить простий. фактично ми його виконуємо при написанні програми. Ось декілька прикладів: goal: - curcor(R,C), R1 = R + 1, curcor(R1,C). В першому виклику предикату cursor дві змінні R і C - вільні. що означає - предикат cursor буде викликатися потоковим зразком cursor (o,o). Змінні вільні, бо зустрічаються вперше. Аналізатор потоку взнає також, що, якщо змінна не використовується в голові фрази, тоді ця змінна буде вихідним аргументом в першому предикатному виклику в тілі фрази. У виразі R1=R+1 аналізатор потоку встановлює, що змінна R прив.язана, тому що з.являється з предикату cursor. Якщо б вона була вільною, тоді б видавалось повідомлення про помилку. R1 стане після цього виклику відомим аргументом. В останньому виклику cursor змінні R1 і С зустрічались попередньо, тому вони обробляються як аргументи входу, а виклик буде мати зразок потоку cursor (i,i). Коли викликається предикат, визначений користувачем, тоді він обробляється аналогічно стандартному предикату. Наприклад, predicates changeattribute(Integer, Integer) clauses changeattribute(NewAttrib, OldAttrib):- attribute(OldAttrib), attribute(NewAttrib). goal changeattribute(112, Old), write(|Hello|), attribute(Old), write(|there|). В розділі goal перший виклик предикату changeattrib зроблено потоковим зразком типу changeattrib(i,o) (тому що перший аргумент відомий - 112, а другий Old - ні). Звідки, в фразі для changeattrib змінна NewAttrib буде аргументом входу, а OldAttrib - аргументом виходу. Але, якщо потоковий аналізатор зустрічає першу підціль attribute(OldAttrib), тоді предикат attribute буде викликатись потоковим зразком attribute (o), а другий виклик attribute буде мати потоковий зразок attribute(i). Кінцевий виклик attribute в goal будет мати потоковий зразок входу, тому що Old з.являється із changeattrib. 10.2.Керування потоковим аналізом. Якщо потоковий аналізатор взнає, що стандартний предикат викликається не існуючим потоковим зразком, тоді видається повідомлення про помилку. Це може допомогти ідентифікувати нісенітні потокові зразки при створенні предикатів користувача, які використовують стандартні предикати. Наприклад, якщо ви використовуєте предикат Z = X + Y де змінна Х або Y не зв.язана, тоді потоковий анализатор видасть повідомлення про помилку: не існує потокового зразка для цього предикату. Для керування такою ситуацією ми можемо використовувати стандартні предикати free і bound. Припустимо, ми хочемо написати предикат plus для реалізації дії додавання при любих можливих потокових зразках. Програма зображена на малюнку 10.1 реалізує такий предикат. predicates plus(integer, integer, integer) num(integer) clauses plus(X,Y,Z) :- bound(X), bound(Y), Z=X+Y. /* (i,i,o) */ plus(X,Y,Z) :- bound(Y), bound(Z), X=Z-Y. /* (o,i,i) */ plus(X,Y,Z) :- bound(X), bound(Z), Y=Z-X. /* (i,o,i) */ plus(X,Y,Z) :- free(X), free(Y), bound(Z), num(X), Y=Z-X. /* (o,o,i) */ plus(X,Y,Z) :- free(X), free(Z), bound(Y), num(X), Z=X+Y. /* (o,i,o) */ plus(X,Y,Z) :- free(Y), free(Z), bound(X), num(Y), Z=X+Y. /* (i,o,o) */ plus(X,Y,Z) :- free(X), free(Y),free(Z), num(X), num(Y),Z=X+Y. /* (o,o,o) */ /* Генератор чисел, які починаються з нуля */ num(0). num(X) :- num(A), X = A+1. Мал.10.1. 10.3. Стиль програмування. В цьому розділі ми дамо рекомендації для написання елегантних і ефективних програм на Пролозі. Для виміру ефективності програми традиційно використовують два параметри: пам.ять і час. В Пролозі на покращання цих оцінок значною мірою впливає відміна хвостової рекурсії. Розглянемо відомий нам предикат member: member (X, [X|_]). member (X,[_|Y]): member (X,Y) Ітеративна операція перевірки або генерації елементів потрібного списку проводиться рекурсивним чином, тому стекова пам.ять (а відповідно і час виконання) повністю залежить від рекурсії. Припустимо, що предикат demopred описується так: demopred (X,Y): - ... , member (A,B), test (A), ... При активізації member спочатку система повинна запам.ятати, що після успішного виконання member керування потрібно передати предикату test. Тому, адреса test повинна бути збережена в стеці. Для кожного рекурсивного звертання до member система запам.ятовує адресу, до якої повинен повернутись предикат member після успішного завертання цього предикату. Враховуючи, що між member (X,[_,Y]):- і рекурсивним зверненням member(X,Y) не має точок повернення до попереднього стану, не має необхідності зберігати адресу member в стеці декілька разів. Достатньо запам.ятати, що після успішного завершення предикату member керування повинно бути передане предикату test. Це і буде відміною хвостової рекурсії. Там, де система не може відмінити рекурсію, програміст може зробити це сам, використовуючи наступні правила. Правило1. Краще використовувати більше змінних, ніж предикатів. Це правило знаходиться часто в прямому конфлікті з наглядністю програми. В багатьох випадках декларативний стиль Прологу приводить до гіршого коду в порівнянні з процедурними мовами. Наприклад, якщо ви пишете предикат, для перестановки елементів списку, тоді такий фрагмент коду, як: reverse(X,Y):- reverse1([],X,Y). /*More efficient*/ reverse1(Y, [], X). reverse1(X1, [U | X2], Y):- reverse1([U|X1],X2,Y). пред.являє менше вимог до стеку, ніж використання додатково предикату append: reverse([],[]). reverse([U | X], Y):- reverse(X,Y1), append(Y1,[U],Y). append([],Y,Y). append([U|X],Y,[U|Z]):-append(X,Y,Z). Правило 2. При впорядкуванні підцілей в правилі, першими розміщуйте підцілі з найбільш зв.язаними змінними. Наприклад ви пишете предикат для вирішення системи рівнянь (Х + 1 = 4 ( (Х + Y = 5 використовуючи метод |генеруй_ і_перевіряй|: solve(X,Y):- /*кращій варіант*/ num(X), plus(X, 1, 4), num(Y), plus(X, Y, 5). Тоді він буде кращим за наступний фрагмент : solve(X,Y):- /*гірший варіант*/ num(X), num(Y), plus(X, Y, 5), plus(X, 1, 4). Предикати num і plus визначались нами раніше. Правило 3. Коли не існує рішень, пробуйте перевіряти, що виконання видасть повідомлення про |неуспіх| эффективно. Припустимо, що ми хочемо написати предикат singlepeak, який перевіряє наявність |піку| серед списку цілих чисел. Іншими словами, числа повинні зростати до одного максимуму, а потім спадати. Для такого предикату виклик singlepeak ([1,2,5,7,11,8,6,4]). буде успішним, тоді як виклик singlepeak ([1,2,3,9,6,8,5,4,3]). видасть повідомлення |неуспіх|. Наступне визначення для singlepeak не враховує Правило 3, тому що наявність в списку однієї |вершини| проводиться тільки у випадку, коли append розбиває список на різноманітні декомпозиції: singlepeak(X):- append(X1,X2,X), up(X1), down(X2). up(_). up([U,V|Y]):- U < V, up([V,Y]). down([]). down([U]). down([U,V|Y]):- U > V, down ([V|Y]). Можна також запропонувати варіанти, які враховують настанови Правила3: singlepeak([]). singlepeak([U,V|Y]):- U < V, singlepeak([U|Y]). singlepeak([U,V|Y]):- U > V, down([V|Y]). down([]). down([U]). down([U,V|Y]):- U < V, down ([V|Y]). або ж варіант: singlepeak([],_). singlepeak([U,V|W],up):- U < V, singlepeak([V|W],Up). singlepeak([U,V|W],_):- U > V, singlepeak([V|W],Down). Правило 4. Механізм уніфікації повинен виконувати як можна більше роботи. Наприклад, для перевірки на рівність двох списків можна використати наступний фрагмент програми: equal([],[]). equal([U|X],[U|Y]):-equal(X,Y). aле в цьому немає потреби, тому що предикат equal(Х,Х) за рахунок механізму уніфікації виконає всю потрібну роботу. Правило 5. Для повтору краще використовуйте бектрекінг ніж рекурсію. Бектрекінг зменшує стекові вимоги. Ідея заключається у тому, щоб використовувати конструкцію типу repeat...fail замість рекурсії. Наприклад, для повторного обчислення деякого предикату process(X,Y) можна використати наступну послідовність предикатів: run:-readln(X), process(X,Y), write(Y), run. Але комбінація repeat...fail зменшує необхідність кінечного рекурсивного виклику. Визначивши repeat. repeat:-repeat. ми можемо перевизначити run без рекурсії: run:-repeat, readln(X), process(X,Y), write(Y), fail. Тут, fail примушує Пролог виконувати бектрекінг в repeat, який завжди виконується успішно. Література. 1. И. Братко. Программирование на языке Пролог для искусственного интеллекта. Москва, Мир, 1990. 2. Дж. Малпас. Реляционный язык Пролог и его применение. Москва, Мир, 1990.
