Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Лекції з дисципліни „Інформатика: програмування задач штучного інтелекту”

Тема 1. Вступ

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

Галузі застосування Пролога.

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

Ї Будування експертних систем (ЕС) і баз знань ЕС.

Ї Виведення теорем, перевірка різноманітних теорій і будування пакетів у галузі штучного інтелекту, де потрібні властиві Прологу можливості проводити дедуктивні міркування.

Ї Побудова пакетів, основаних на символьній обробці.

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

Ї Реалізація динамічних баз даних.

Принцип роботи Пролога.

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

Знання Пролога - це кінцева сукупність фактів і правил, що задаються в програмі.

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

Структура програм на Пролозі.

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

Ї Імена і структури об'єктів, що беруть участь у даній задачі.

Ї Імена відношень, існуючих між об'єктами (предикати).

Ї Факти і правила (речення), що характеризують ці відношення.

Речення Пролога складаються з голови та тіла і бувають трьох типів: факти, правила та запити.

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

відношення(об'єкт1,об'єкт2,...,об'єктN).

Приклади. людина(„Гіві”).

подобається(„Гіві”,„Єва”).

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

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

Приклад.дитина(Y,X):-батько(X,Y);

мати(X,Y).

Заголовок - це відношення (факт), істинність якого залежить від істинності списків умов в тілі правила. Це називається відношенням залежності.

Символ „:-” (якщо) розділяє заголовок і тіло правила.

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

Якщо підцілі тіла правила розділені комою, - це означає логічну кон'юнкцію, тобто повинні задовільнюватися всі підцілі, якщо ж підцілі розділені крапкою з комою, - це означає логічну диз'юнкцію, тобто повинна задовільнюватися хоча б одна частина тіла правила - до або після крапки з комою.

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

<підціль1>,<підціль1>,...,<підцільN>.

Приклад.дитина(Y,”Петро”).

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

Тема 2. Основні розділи програми на Пролозі

Звичайна програма на Пролозі включає три або чотири програмних розділи:

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

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

Ї розділ мети (goal);

Ї розділ виразів (clauses).

Розділ clauses (факти і правила).

Це ядро програми, в якому містяться факти і правила, якими оперує Пролог, намагаючись досягти мети.

Вирази, що стосуються певного предикату, повинні розміщуватися в розділі clauses разом. Послідовність таких виразів, що визначають предикат, називають процедурою.

Приклад.

дитина(Y,X):-батько(X,Y).

дитина(Y,X):-мати(X,Y).

Кожне речення розділу clauses обов'язково повинне закінчуватись крапкою.

Розділ predicates (оголошення предикатів).

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

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

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

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

Оголошення предикатів має такий вигляд:

predicates

ім'я_предиката(тип_аргумента1,тип_аргумента2,...,тип_аргументаN)

де тип_аргумента1,тип_аргумента2,...,тип_аргументаN - або стандартні домени, або домени, оголошені в розділі domains.

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

Арність предиката - це число його аргументів. Можуть бути предикати з однаковим іменем але з різною арністю. Такі предикати трактуються як цілком різні і тому повинні відповідно групуватися в розділах predicates та clauses.

Приклад.

domains

людина=symbol

predicates

батько(людина)

батько(людина,людина)

clauses

батько(Людина):-батько(Людина,_).

батько(„Пітер”,”Моніка”).

батько(„Стівен”,”Алекс”).

goal

батько(Людина)

Людина=”Пітер”

Людина=”Стівен”

Розділ domains (оголошення типів).

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

Основними стандартними доменами або типами в Пролозі є: char, integer, real, string, symbol та file.

Оголошення доменів простих об'єктів має такий синтаксис:

domains

тип_аргумента1,..., тип_аргументаN=<стандартний домен>

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

Приклад.

Федір - це чоловік, якому 45 років.

1.predicates

людина(symbol,symbol,integer)

2.domains

ім'я,стать=symbol

вік=integer

predicates

людина(ім'я,стать,вік)

Другий варіант більш зручний і зрозумілий.

Розділ gool (запити).

В Пролозі використовують два типа мети: внутрішня (вбудована мета), що розміщується в розділі gool, і зовнішня мета, що вводиться в рамках вікна Dialog після запуску програми, якщо внутрішня мета не використовується.

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

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

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

У випадку завдання зовнішньої мети Пролог шукає всі рішення і виводить значення змінних.

Коментарі.

Коментарі в Пролозі повинні починатися з символів „/*” і закінчуватись „*/”. Те, що написано між цими двома парами символів компілятором ігнорується. Як альтернативу для однорядкових коментарів можна використовувати символ „%”. Все, що знаходиться праворуч від цього символа і до кінця рядку, вважається коментарем. Включення коментарів, що пояснюють ті чи інші аспекти вашої програми є гарним стилем програмування.

Інші розділи програми.

Розділ database.

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

Розділ constants.

В програмі на Пролозі можна оголошувати і використовувати символьні константи. Розділ оголошення констант починається ключовим словом constants. Після цього слідують самі оголошення з дотриманням наступного синтаксису:

<ідентифікатор>=<макровизначення>

де ідентифікатор - це ім'я константи, а макровизначення - це те, що цьому імені відповідає. Кожне макровизначення закінчується символом „новий рядок”. Тому в одному рядку повинна міститися одна константа. На оголошені таким чином константи після цього можна посилатися в програмі.

Приклад.

constants

нуль=0

пі=3.141592653

їжа=3

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

Обмеження при використанні символьних констант.

Ї Визначення константи не може посилатися саме на себе.

Приклад. кіт=5+кіт

Ї Система не розрізняє у визначенні константи великі і малі літери, тому при використанні констант в розділі clauses їхня перша літера повинна бути малою для запобігання тлумачення константи як змінної.

Ї В програмі може бути декілька розділів констант, але всі константи повинні оголошуватися до їхнього використання в програмі.

Ї Ідентифікатори констант є глобальними і можуть оголошуватися тільки один раз.

Розділ global.

Цей розділ використовується для оголошення в програмі деяких доменів, предикатів і виразів глобальними на відміну від локальних. Це можна зробити, зформувавши в самому початку програми окремі розділи global domains, global predicates, global clauses.

Директиви компілятора.

В Пролозі передбачено декілька директив компілятора, що можуть включатись в програму для того, щоб під час компіляції текст програми трактувався певним чином. Більшість директив можуть бути встановлені як безпосередньо в тексті програми, так і інтерактивно звикористанням елементу меню Compiler Directive меню Options.

Директива include.

Щоб зекономити на введенні процедур, що часто використовуються, необхідно створити окремий файл з цими процедурами і застосувати директиву include. Для цього достатньо розмістити у вхідному тексті наступний рядок:

include „file_name.pro”

Директиви trace і shorttrace.

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

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

Тема 3. Змінні. Встановлення відповідності

Змінні використовуються в запитах для вказівки невідомих параметрів, і в правилах для встановлення залежності між об'єктами.

Змінні, що використовуються в заголовку правила, обов'язково повинні бути задіяні в його тілі.

Приклад.дитина(Y,X):-батько(X,Y);

мати(X,Y).

Імена змінних в Пролозі повинні починатися з великої латинської літери, після якої можуть слідувати будь-які латинські літери, цифри або символи підкреслювання.

Правильні імена	Не правильні імена
P_10_11_2001	red
VarNAME	„катастрофа”

Ретельний підбір імен змінних робить програму більш читабельною.

Зв'язування змінних.

В Пролозі не має оператора привласнення „:=”. Змінні в Пролозі одержують значення в результаті встановлення відповідності з константами в фактах і правилах.

Доки змінна не має якого-небудь значення, вона називається вільною. На початку виконання програми всі змінні є вільними. Коли ж таке значення з'являється - змінна стає зв'язаною, але не назавжди, а лише на той час, що необхідний для пошуку відповіді на запит. Після цього Пролог звільнює її і повертається назад для пошуку альтернативних рішень.

В Пролозі не можна зберігати значення шляхом привласнення значення змінній. Змінні використовуються як частина процесу порівняння зі зразком, а не як засіб зберігання інформації.

Приклад. ch03ex03.pro

predicates

подобається(symbol,symbol)

clauses

подобається(„Олена”,”читання”).

подобається(„Іван”,”комп'ютери”).

подобається(„Леонід”,”бадмінтон”).

подобається(„Борис”,”плавання”).

подобається(„Борис”,”читання”).

goal:подобається(Людина,”читання”),

подобається(Людина,”плавання”)

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

Далі, щоб повністю задовільнити запит, необхідно знайти рішення для його другої частини. Оскільки змінна Людина зв'язана значенням „Олена” Пролог повинен знайти факт подобається(„Олена”,”плавання”). Пошук цього факту Пролог веде з самого початку програми, але відповідність не встановлюється, оскільки такого факту в програмі не має. Тобто коли змінна Людина зв'язана значенням „Олена” істинність другої частини правила не досягається. Тому Пролог звільнює змінну Людина і намагається знайти інше рішення першої частини запиту. Цей пошук починається з позиції показчика в списку фактів.

Пролог шукає іншу людину, якій подобається читання і знаходить факт подобається(„Борис”,”читання”). Змінна Людина тепер зв'язується значенням „Борис”, а Пролог намагається задовільнити підціль подобається(„Борис”,”плавання”). В даному випадку відповідність встановлюється і Пролог видає наступний результат:

Людина=”Борис”

1 solution

Анонімні змінні.

Анонімні змінні дозволяють вилучити з програми непотрібну інформацію. Якщо з запиту потрібна тільки деяка інформація, то для ігнорування непотрібних значень як раз і використовують анонімні змінні. В Пролозі анонімна змінна позначається символом підкреслювання „_”. Анонімна змінна може використовуватися на місці якої-небудь іншої змінної. Різниця буде лише в тому, що анонімній змінній ніколи не буде привласнене значення.

Приклад.

predicates

батько(людина)

батько(людина,людина)

clauses

батько(Людина):-батько(Людина,_).

батько(„Пітер”,”Моніка”).

батько(„Стівен”,”Алекс”).

goal

батько(Людина)

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

Людина=„Пітер”

Людина=„Стівен”

2 solution

Анонімні змінні можуть використовуватися в фактах.

Приклад.

володіє(_,”туфлі”).

їсть(_).

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

Встановлення відповідності (уніфікація).

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

Уніфікація - це процес встановлення відповідності між двома предикатами і зв'язування (конкретизація) вільних змінних з метою зробити предикати ідентичними.

Цей механізм необхідний для того, щоб Пролог міг встановлювати які вирази викликати і якими значеннями конкретизувати змінні. Основні правила уніфікації або встановлення відповідності:

Ї Пошук відповідності починається з самого початку програми.

Ї Для нового виклику пошук відповідності починається теж з самого початку.

Ї Після успішно завершеного виклику робиться спроба задовільнити наступну ціль.

Ї Після зв'язування змінної в виразі єдиним способом її звільнення є використання пошуку з поверненням.

Тема 4. Пошук з поверненням. Керування процесом пошуку рішень

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

Приклад.

ch05ex03.pro

domains

дитина=symbol

вік=integer

predicates

гравець(дитина,вік)

clauses

гравець(„Петро”,9).

гравець(„Павло”,10).

гравець(„Роман”,9).

гравець(„Тетяна”,9).

goal: гравець(Партнер1,9),

гравець(Партнер2,9),

Партнер1<>Партнер2.

Відповідь: Партнер1=”Петро”, Партнер2=”Роман”;

Партнер1=”Петро”, Партнер2=”Тетяна”;

Партнер1=”Роман”, Партнер2=”Петро”;

Партнер1=”Роман”, Партнер2=”Тетяна”;

Партнер1=”Тетяна”, Партнер2=”Роман”;

Партнер1=”Тетяна”, Партнер2=”Петро”.

Основні принципи пошуку з поверненням.

Ї Підцілі повинні бути задовільнені з першої до останньої.

Ї Предикатні вирази перевіряються в тій послідовності, в якій вони розміщені в програмі.

Ї Коли підціль приводиться у відповідність із заголовком правила, повинне бути задовільнено тіло цього правила. Це тіло формує новий набір підцілей, що повинні бути задовільнені.

Ї Мета вважається задовільненою, якщо відповідний факт знаходиться для кожного з листів дерева мети.

Для досягнення підцілі Пролог починає пошук з першого виразу, що визначає даний предикат. При цьому можливі два випадки:

1. Пролог знаходить відповідний вираз. При цьому відбувається наступне:

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

б) всі вільні змінні в підцілі, з якими встановлюється відповідність у виразі, зв'язуються відповідними значеннями;

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

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

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

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

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

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

Приклад.

ch03ex04.pro

predicates

подобається(symbol,symbol)

clauses

подобається(„Олена”,”читання”).

подобається(„Іван”,”комп'ютери”).

подобається(„Леонід”,”бадмінтон”).

подобається(„Борис”,”плавання”).

подобається(„Борис”,”читання”).

goal

подобається(Людина,”читання”),

write(Людина, „подобається читання”,/n),

fail.

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

Предикат write не може дати нові рішення, тому Пролог повинен повернутися до першої підцілі запиту.

Відсікання (відвертання повернення).

Відсікання позначається знаком оклику „!”. Дія відсікання полягає в тому, що через нього неможливо виконати повернення тому, що він змушує Пролог „забути” всі точки повернення розташовані до відсікання. В програмі відсікання розміщуються, як підціль в тілі правила. Коли обробка проходить через відсікання, виклик через відсікання відразу ж визнається успішним, після чого викликається наступна підціль, якщо вона є. Після проходження відсікання в прямому напрямку, повернутися до попередніх підцілей поточного виразу стає неможливим, неможливим стає і повернення до інших виразів, які визначають предикат, що обробляється в поточний момент (містить відсікання). Тобто предикат відсікання „!” встановлює бар'єр, що забороняє виконати повернення до всіх альтернативних рішень поточної підцілі. Однак наступні підцілі можуть створювати нові точки повернення і завдяки цьому створити умови для пошуку нових рішень.

Відсікання має два основних призначення:

1. Коли заздалегіть відомо, що певні варіанти ніколи не дадуть прийнятних рішень, то пошук альтернативних рішень буде простою витратою часу. Якщо в такій ситуації використати відсікання, то в результаті програма буде працювати швидше і займе менше пам'яті. Таке відсікання називається „зеленим”. Якщо його вилучити з програми логіка її роботи не порушиться.

2. Коли відсікання відвертає розгляд альтернативних підцілей, що вимагає логіка програми, то воно називається „червоним”. Якщо його вилучити з програми, то вона або взагалі не буде працювати, або буде видавати неправильні результати.

Відвертання, повернення до попередньої цілі в програмі.

r:-a,b,!,c.

r:-d.

де r -заголовок правила, a,b,c,d - підцілі.

Використовується у випадках, коли нас задовольняє перше знайдене рішення підцілей a і b. Хоча Пролог з використанням поверенення може знайти декілька рішень, але таке повернення через відсікання не дозволяється. Не дозволяється також повернення до іншого виразу, що визначає предикат r.

Приклад.

сестра(,):-мати(Z,X),

мати(Z,Y),

жінка(Y),

X<>Y,!;

батько(Z,X),

батько(Z,Y),

жінка(Y),

X<>Y.

Використання правил як варіантних операторів.

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

ch05ex13.pro

predicates

дія(integer)

clauses

дія(1):-write(„Ви ввели 1”).

дія(2):-write(„Ви ввели 2”).

дія(3):-write(„Ви ввели 3”).

дія(X):-X<>1,X<>2,X<>3,

write(„Цієї цифри я не знаю”).

goal

write(„Введіть цифру від 1 до 3”),

readint(Вибір),

дія(Вибір).

Користувач вводить цифру 1, 2 або 3, що призводить до встановлення відповідності з одним з перших трьох правил.

Четверте правило уніфікується завжди, коли до нього доходить справа. При цьому Х пов'язується значенням, з яким виконується звернення до правила. Підцілі X<>1, X<>2, X<>3 призначені для перевірки того, що не спрацювало жодне з попередніх правил.

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

Відсікання як безумовний перехід.

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

Якщо в кожному правилі встановити відсікання, то альтернативні варіанти розглядатися не будуть, що зекономить час і ресурси ЕОМ. Відсікання немов би каже, що якщо ви попали сюди, то жодне повернення в цьому правилі робити не потрібно, як не потрібно розглядати альтернативи всьому даному правилу. Альтернативі при цьому можливі але на більш високому рівні. Наприклад, якщо поточне правило буде викликане іншим правилом, а у останнього є альтернативи, то ці альтернативи доступні для розгляду. Відсікання виводить з розгляду тільки альтернативи всередені правила і альтернативи всьому цьому правилу.

З урахуванням цього попередня програма матиме наступний вигляд.

ch05ex14.pro

predicates

дія(integer)

clauses

дія(1):-!,write(„Ви ввели 1”).

дія(2):-!,write(„Ви ввели 2”).

дія(3):-!,write(„Ви ввели 3”).

дія(_):-write(„Цієї цифри я не знаю”).

Відсікання в даній програмі називають „червоними відсіканнями”. Якщо останнє правило залишити як у попередньому прикладі дія(X):-X<>1,X<>2,X<>3,write(„Цієї цифри я не знаю”), то відсікання будуть „зеленими”.

Предикат not.

Предикат not закінчується успішно коли не можна досягти істинності підцілі всередені предикату. Він має наступний синтаксис:

not(підціль).

Якщо підціль задовільнюється, то предикат not не задовільнюється і навпаки. Це призводить до того, що зв'язані змінні не можуть більше зв'язуватися в межах not. Це означає, що всі змінні, які використовуються в межах not, на момент виклику повинні бути зв'язаними. Останнє пояснюється тим, що для того, щоб Пролог міг зв'язати вільні змінні в підцілі, остання повинна успішно уніфікуватися з іншим виразом. Для того, щоб коректно обробляти вільні змінні в межах not слід використовувати анонімні змінні.

Приклад 1.

подобається(„Борис”,Хтось):-подобається(„Ольга”,Хтось),

not(ненавидить(„Борис”,Хтось)).

Тут стверджується, що Хтось подобається Борису, якщо він подобається Ользі і його Борис не ненавидить. В цьому прикладі перед викликом предикату not змінна Хтось пов'язується значення підціллю подобається(„Ольга”, Хтось), тому це правило працює вірно.

Приклад 2.

подобається(„Борис”,Хтось):-not(ненавидить(„Борис”,Хтось)), подобається(„Ольга”,Хтось).

В цьому випадку Пролог видасть помилку, бо змінна Хтось на момент виклику not є вільною. Навіть якщо в цьому виразі замість змінної Хтось поставити анонімну змінну, то результат всеодно буде не вірним, хоча повідомлення про помилку виведено не буде.

Приклад 3.

подобається(„Борис”,Хтось):-not(ненавидить(„Борис”,_)), подобається(„Ольга”,Хтось).

В цьому варіанті стверджуєтьсяє, що Борису подобається Хтось, якщо він нікого не ненавидить і Хтось подобається Ользі, що не зовсім вірно.

Повернення значень розрахунків.

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

Приклад.

goal

подобається(„Борис”,Хтось)

Факт подобається(„Борис”,”Ольга”) повертає інформацію цілі подобається(„Борис”,Хтось) шляхом зв'язування змінної Хтось значенням „Ольга”.

Розглянемо інший приклад.

ch05ex15.pro

predicates

класифікувати(integer,symbol)

clauses

класифікувати(0, „нуль”).

класифікувати(X, „негативне”):-X<0.

класифікувати(X, „позитивне”):-X>0.

Перший аргумент класифікувати повинен бути або константою або змінною. Другий аргумент може бути як зв'язаним так і не зв'язаним і в залежності від значення першого аргументу зіставлятися зі значенням „нуль”, „позитивне” або „негативне”.

Приклади запитів.

Чи є 45 позитивним числом: класифікувати(45, „позитивне”).

Чи є 45 негативним числом: класифікувати(45, „негативне”).

Яким числом є 45: класифікувати(45,Яке).

Між метою класифікувати(45,Яке) і заголовком першого правила відповідність не встановлюється оскільки 045. Тому мета зіставляється з заголовком другого виразу: Х - пов'язується значенням 45, а Яке - значенням „негативне”. Але в зв'язку з тим, що перевірка X<0 дасть невдале закінчення, Пролог знову звільнить зв'язані змінні. Далі мета зіставляється з заголовком третього правила: Х - пов'язується значенням 45, а Яке - значенням „позитивне”. Перевірка X>0 дасть вдале закінчення. Оскільки це позитивне рішення повернення для подальшого пошуку не робиться, здійснюється перехід у викликаючу процедуру (в даному випадку це мета) і, оскільки змінна Яке відноситься до викликаючої процедури, остання може скористатися її значенням.

Тема 5. Типи даних

Основні стандартні домени в Пролозі.

№	Домен	Опис
1.	char (літерний)	символ, укладений між двома апострофами.
2.	integer (цілій)	цілі числа в діапазоні від -32768 до 32767
3.	real (речовинний)	речовинні числа в діапазоні від 1*е-307 до 1*е307. Формат чисел: <+/->DDDDD<.>DDDDDDD<e<+/->DDD>
4.	string (рядковий)	будь-яка послідовність символів, укладених в подвійні лапки, довжиною до 255 символів
5.	symbol (символьний)	для цього типу передбачено два формати: послідовність латинських літер, цифр, символів підкреслення, перший з яких - мала літера; послідовність будь-яких символів в подвійних лапках
6.	file (файловий)	допустиме ім'я файлу

Типи даних.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Прості типи даних.

Простими об'єктами даних є або зміна, або константа. Константа може бути символом (char), числом (integer, real) або атомом (symbol, string).

Змінні, як об'єкти даних.

Змінні повинні починатися з великої літери, або знаку підкреслювання.

Змінна може зв'язуватися з будь-яким допустимим аргументом або об'єктом даних. Змінні в Пролозі - локальні, а не глобальні. Тобто, якщо в кожному з двох виразів є змінна X, то це дві різні змінні. Вони можуть зв'язуватися між собою, якщо зводяться в процесі уніфікації, але, як правило, взаємного впливу не мають.

Константи, як об'єкти даних.

Значення константи - це її ім'я.

Символи.

Символи мають тип char і складаються з символів ASCII, що виводяться і не виводяться на друк.

Є два способи оголошення символу, як константи: безпосередньо або встановивши перед ним перехідний символ «/».

Якщо необхідно використати в якості символьної константи зворотній флеш, подвійні або одинарні лапки, то попереду будь-якого з цих символів необхідно встановлювати перехідний символ: '\\', '\”', '\''.

Ряд символьних констант з перехідним символом виконує спеціальні функції:

'\n' - новий рядок;

'\t' - горизонтальна табуляція;

'\126' - замінюється символом таблиці ASCII-кодів, що має відповідний номер.

Числа.

В Пролозі є два типи чисел: integer (цілі) та real (речовинні). Речовинні числа використовуються в Пролозі рідко, тому що він не призначений для роботи з такими числами.

Атоми.

В Пролозі є два типи атомів: symbol і string. Атоми повинні складатися з ланцюжка літер, цифр і символів підкреслення, починаючи з малої літери, або зі спеціальних символів, чи будь-яких символів, взятих у лапки.

Пролог виконує автоматичне перетворення типів symbol і string, якщо це можливо.

Атоми symbol починаються з латинської малої літери, а атоми string беруться в подвійні лапки.

Приклади.

symbol	string
yurij_Gagarin	“Ukraine”
a	“a”
turbo_pascal	“Турбо паскаль”

Складові об'єкти і функтори.

Складові об'єкти даних дозволяють трактувати декілька елементів інформації як один об'єкт таким чином, що ці елементи можуть бути знов легко відділені.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Складовий об'єкт дата включає елементи число, місяць і рік.

На Пролозі цей об'єкт можна виразити наступним чином:

дата(9, „жовтня”, 2002)

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

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

Аргументи складового об'єкту самі можуть бути складовими.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Приклад.

На Пролозі такий об'єкт описується наступним чином:

програмування мова пролог

день_народження(людина(„Юрій”, „Марусич”),дата(15, „липня”,2002))

Оголошення доменів складових об'єктів.

Узагальнений запис оголошень складових об'єктів має наступний вигляд:

домен=альтернатива1(Д,Д,...);

альтернатива2(Д,Д,...);

. . .

де альтернатива1(Д,Д,...), альтернатива2(Д,Д,...) - це довільні, але різні функтори; Д,Д,...,Д - список стандартних доменів, або доменів, проголошених раніше.

Приклад.

ch06ex04.pro

domains

об'єкти=книга(назва,автор);

кінь(призвісько);

човен;

особистий_рахунок(баланс)

назва,автор,призвісько=symbol

баланс=real

predicates

володіє(symbol,об'єкти)

clauses

володіє(„іван”,книга(„Му-му”, „Тургенев”)).

володіє(„іван”,кінь(„Пегас”)).

володіє(„іван”,човен).

володіє(„іван”,особистий рахунок(10000)).

Якщо запустити програму з запитом володіє(„іван”,Річ) Пролог дасть наступну відповідь:

Річ=книга(„Му-му”, „Тургенев”)

Річ=кінь(„Пегас”)

Річ=човен

Річ=особистий рахунок(10000)

Уніфікація складових об'єктів.

Складовий об'єкт можна уніфікувати або з простою змінною або з іншим складовим об'єктом такого ж типу. Це означає, що складовий об'єкт можна використати для передачі всієї сукупності елементів як одного об'єкту або для виділення його окремих елементів.

Приклад.

дата(9, „жовтня”, 2002)Х

Результат: Х=дата(9, „жовтня”, 2002).

дата(9, „жовтня”, 2002) дата(X,Y,Z)

Результат: Х=9, Y=„жовтня”, Z=2002.

Приклад використання складових об'єктів.

Розглянемо ведення бази даних телефонних номерів.

predicates

список_тел(symbol, symbol, symbol, symbol, integer, integer)

/* ім'я, прізвище, телефон, місяць, день і рік народження */

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

ch06ex03.pro

domains

ім'я=людина(symbol,symbol) /* ім'я,прізвище */

день_народження(symbol,integer,integer) /* день,місяць,рік */

номер=symbol

predicates

список_тел(ім'я,номер,день_народження)

отримати_дні_народження_по_місяцю

перетворити_місяць(symbol,integer)

перевірити_місяць(integer,день_народження)

записати_людину(ім'я)

clauses

отримати_дні_народження_по_місяцю:-

makewindow(1,7,7, „Дні народження цього місяця”, 0,0, 25,80),

write(„Ім'я \t \t Прізвище \n”),

date(_,Цей_місяць,_),

список_тел(Людина,_,Дата),

перевірити_місяць(Цей_місяць,Дата),

записати_людину(Людина),

fail.

отримати_дні_народження_по_місяцю:-

write(„\n \n Для продовження натисніть клавішу”),

readchar(_).

записати_людину(людина(Ім'я,Прізвище)):-

write(„ ”,ім'я, „\t \t”, Прізвище), nl.

перевірити_місяць(Місяць,дата((Місяць1,_,_)):-

перетворити(Місяць1,Місяць2)),

Місяць=Місяць2.

список_тел(людина(„Юрій”, „Марусич”),”71-95-06”, дата(лип, 15,1972)).

список_тел(людина(„Сергій”, „Хоменко”),”71-93-83”, дата(вер, 12,1971)).

список_тел(людина(„Михайло”, „Назаренко”),”71-93-83”, дата(січ,2,1967)).

перетворити(січ,1).

перетворити(лют,2).

перетворити(бер,3).

перетворити(кві,4).

перетворити(тра,5).

перетворити(чер,6).

перетворити(лип,7).

перетворити(сер,8).

перетворити(вер,9).

перетворити(жов,10).

перетворити(лис,11).

перетворити(гру,12).

Для запуску програми необхідно задати мету

отримати_дні_народження_по_місяцю

Основна робота програми зосереджена на предикаті отримати_дні_народження_по_місяцю:

1. Спочатку створюється вікно для відображення результатів.

2. Після цього виводиться заголовок таблиці результатів.

3. Вбудований предикат date використовується для зв'язування змінної Цей_місяць номером поточного місяця.

4. Береться перша людина зі списку абонентів і змінні Людина та Дата пов'язуються відповідними значеннями.

5. Предикат перевірити_місяць аналізує змінну Дата, порівнюючи її з поточним місяцем. Перший аргумент відношення перевірити_місяць зв'язується зі значенням змінної Цей_місяць, а змінна Місяць1 другого аргументу - значенням місяця народження.

6. Далі символьне представлення місяця (змінна Місяць1) перетворюється в ціле значення (змінна Місяць2), яке після цього порівнюється з поточним місяцем. Якщо порівняння дасть збіг, то підціль задовільнюється і буде виконане повернення для пошуку іншої людини.

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

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

Багаторівневі складові об'єкти.

Пролог дозволяє будувати складові об'єкти на декількох рівнях.

Приклад.

книга(„Гадке каченя”, „Ганс-Христіан”, „Андерсен”)

Замість прізвища автора можна було б ввести нову структуру, що включає його ім'я та прізвище.

Приклад.

книга(„Гадке каченя”,автор(„Ганс-Христіан”, „Андерсен”))

Для використання таких об'єктів необхідно зробити наступні оголошення:

domains

об'єкти=книга(назва,автор)/* 1-й рівень */

автор=автор(ім'я,прізвище)/* 2-й рівень */

назва,ім'я,прізвище=symbol

Один оператор розділу доменів описує тільки один рівень дерева об'єкту, а не все дерево.

Оголошення складових змішаних доменів.

Такі оголошення дозволяють використовувати предикати, що:

Ї мають аргумент більш як одного можливого типу;

Ї мають змінну кількість аргументів, кожний з яких певного типу;

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

Багатотипові аргументи.

Щоб предикат Пролога міг сприймати аргумент, що несе інформацію різних типів, необхідно додати оголошення функтору.

Приклад.

domains

вік=ц(integer);

р(real);

с(string)

predicates

ваш_вік(вік)

clauses

ваш_вік(ц(вік)):-write(вік).

ваш_вік(р(вік)):-write(вік).

ваш_вік(с(вік)):-write(вік).

Тема 6. Повторення і рекурсія

Процеси, що повторюються. Реалізація циклів за допомогою пошуку з поверненням.

Пошук з поверненням - це чудовий спосіб отримання всіх альтернативних рішень для поставленої мети.

Але навіть якщо мета не має декількох рішень, повернення можна використати для організації циклів. Для цього використовують конструкцію повторити:

повторити.

повторити:-повторити.

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

Приклад.

Програма ch07ex02.pro використовує повторити для прийому з клавіатури і друку символів доти, доки користувач не натисне клавішу Enter.

predicates

повторити

друкмаш

clauses

повторити.

повторити:-повторити.

друкмаш:-повторити,

readchar(C),

write(C),

char_int(C,13).

Друкмаш працює наступним чином:

1) виконується повторити (не робиться нічого);

2) з клавіатури зчитується символ і змінна С пов'язується його значенням;

3) С виводиться на екран;

4) перевіряється відповідність ASCII-коду С коду Enter (13), - якщо відповідність встановлюється, то робота програми завершується, інакше - відбувається повернення для пошуку альтернатив;

5) ні write, ні readchar не дають альтернатив, тому повернення йде на повторити, яке завжди має альтернативи, відбувається повторення п.п.2-4 доки не буде натиснута клавіша Enter.

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

Рекурсивні процедури.

Іншим спососбом реалізації повторення є використання рекурсії.

Рекурсивна процедура - це процедура, що викликає сама себе.

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

Логіку програми розглянемо на прикладі знаходження факторіалу числа N:

Ї Якщо N=1, то факторіал=1.

Ї В іншому випадку - знайти факторіал числа (N-1), а потім помножити його на N.

Приклад.

ch07ex03.pro

predicates

факторіал(integer,real)

clauses

факторіал(1,1):-!.

факторіал(X,ФактX):-Y=X-1,

факторіал(Y,ФактY),

ФактX=X*ФактY.

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

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

Переваги рекурсії.

1. Простота і компактність виразів.

2. Дозволяє передавати лічильник та інші проміжні результати від однієї ітерації до іншої.

3. Незамінна при обробці списків та інших рекурсивних структур даних.

4. З її допомогою можуть бути виражені алгоритми, які традиційним способом виражені бути не можуть.

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

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

Хвостова рекурсія.

У рекурсії є один великий недолік - вона з'їдає пам'ять. Кожного разу коли одна процедура викликає іншу, робочий стан процедури, що викликає, повинен бути збережений для того, щоб після обробки виклику відновити її стан і продовжити обробку. Це означає, що якщо процедура викликає себе 100 разів, то повинно одночасно зберігатися 100 різних її робочих станів.

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

Для виникнення хвостової рекурсії необхідне виконання наступних двох вимог:

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

2. Перед рекурсивним викликом у виразі немає точок повернення.

Приклад.

predicates

рахунок(real)

clauses

рахунок(N):-write(N),nl,

НовеN=N+1,

рахунок(НовеN).

Приклади псевдохвостової (нехвостової) рекурсії.

1. Якщо рекурсивний виклик не є самим останім кроком, то хвостової рекурсії немає.

predicates

пог_рахунок1(real)

clauses

пог_рахунок1(N):-write(N),nl,

НовеN=N+1,