Мова логічного програмування Visual Prolog

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати


I. Основи мови Visual Prolog

  1. Введення в логічне програмування

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

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

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

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

  1. Синтаксис логіки предикатів

Пропозиції на природній мові

Синтаксис логіки предикатів

Машина гарна

fun (car)

Троянда червона

red (rose)

Білл любить машину, якщо машина красива

likes (bill, Car) if fun (Car)

  1. Факти

На Пролозі описуються об'єкти (objects) і відношення (relations), а потім описує правила (rules), при яких ці ​​відносини є істинними. Наприклад, пропозиція

Білл любить собак. (Bill likes dogs.)

встановлює відношення між об'єктами Bill і dogs (Білл і собаки); цим відношенням є likes (любить). Нижче представлено правило, що визначає, коли пропозиція "Білл любить собак" є істинним:

Білл любить собак, якщо собаки хороші. (Bill likes dogs if the dogs are nice.)

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

Нижче представлено кілька пропозицій на природній мові з відношенням "любить" (likes):

Білл любить Сінді. (Bill likes Cindy)

Сінді любить Білла. (Cindy likes Bill)

Білл любить собак. (Bill likes dogs)

А тепер перепишемо ці ж факти, використовуючи синтаксис Прологу:

likes (bill, cindy).

likes (cindy, bill).

likes (bill, dogs).

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

green (kermit).

girl (caitlin).

  1. Предикати

Ставлення в Пролозі називається предикатом. Аргументи - це об'єкти, які зв'язуються цим відношенням; у факті

likes (bill, cindy).

ставлення likes - це предикат, а об'єкти bill і cindy - аргументи.

Приклади предикатів з різною кількістю аргументів:

pred (integer, symbol)

person (last, first, gender)

run ()

birthday (firstName, lastName, date)

У прикладі показано, що предикати можуть зовсім не мати аргументів.

  1. Правила

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

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

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

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

Сінді любить Сінді. (Cindy likes Cindy)

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

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

likes (cindy, Something): - likes (bill, Something). ilikes (caitlin, Something): - green (Something).

Символ: - має сенс "якщо", і служить для розділення двох частин правила: заголовка і тіла. Можна розглядати правило і як процедуру. Іншими словами, правила

li kes (cindy, Something): - likes (bill, Something).

l i kes (caitlin, Something): - green (Something).

означають: "Щоб довести, що Сінді любить щось, доведіть, що Білл любить це" і "Щоб довести, що Кейтлін любить щось, доведіть, що це щось зелене". З такою "процедурної" точки зору правила можуть "попросити" Пролог виконати інші дії, відмінні від доказів фактів, наприклад, надрукувати що-небудь.

  1. Запити (Цілі)

Описавши в Пролозі кілька фактів, можна ставити питання, що стосуються відносин між ними. Це називається запитом (query) системи мови Пролог. Можна задавати Прологу такі ж питання, які ми могли б поставити вам про ці відносини. Грунтуючись на відомих, заданих раніше факти і правила, ви можете відповісти на питання про ці відносини, в точності так само це може зробити Пролог. На природному мовою ми запитуємо: Does Bill like Cindy? (Білл любить Сінді?) За правилами Прологу ми запитуємо:

likes (bill, cindy).

Отримавши такий запит, Пролог відповість:

yes (та)

тому що Пролог має факт, що підтверджує, що це так. Трохи ускладнивши питання, можна запитати на природній мові: What does Bill like? (Що любить Білл?) За правилами Прологу ми запитуємо:

likes (bill, What).

Необхідно відзначити, що другий об'єкт - What-починається з великої літери, тоді як перший об'єкт - bill - ні. Це відбувається тому, що bill - фіксований, постійний об'єкт - відома величина, a What - змінна.

Змінні завжди починаються з великої літери або знака підкреслення!

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

What = cindy

What = dogs

2 Solutions

Так, як йому відомо, що

likes (bill, cindy).

і

likes (bill, dogs).

Якби ми запитали:

What does Cindy like? (Що любить Сінді?)

likes (cindy, What).

то Пролог відповів би:

What = bill

What = cindy

What = dogs

3 solutions

оскільки Пролог знає, що Сінді любить Білла, і що Сінді любить те ж, що і Білл, і що Білл любить Сінді і собак.

Ми могли б поставити Прологу та інші питання, які можна задати людині. Але питання типу "Яку дівчину любить Білл?" не отримають рішення, тому що Прологу в даному випадку не відомі факти про дівчину, а він не може вивести висновок, заснований на невідомих даних: у цьому прикладі ми не дали Прологу якого-небудь відносини або властивості, щоб визначити, чи є які -які об'єкти дівчатами.

  1. Розміщення фактів, правил і запитів

Припустимо, є наступні факти і правила:

Швидка машина - приємна. (A fast car is fun).

Велика машина - красива. (A big car is nice).

Маленька машина - практична. (A little car is practical).

Біллу подобається машина, якщо вона приємна. (Bill likes a car if the car is fun).

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

Ось приклад, який демонструє, як Пролог використовує правила для відповіді на запити. Подивіться на факти і правила в цій частині програми ch 02 e 01. Pro:

likes (ellen, tennis).

likes (John, football).

likes (torn, baseball).

likes (eric, swimming).

likes (mark, tennis).

likes (bill, Activity): - likes (torn, Activity).

Останній рядок у програмі є правилом. Це правило відповідає пропозиції природної мови:

Біллу подобається заняття, якщо Тому подобається це заняття. (Bill likes an activity if Tom likes that activity)

У даному правилі заголовок - це likes (bill, Activity), а тіло - likes (torn, Activity). Зауважимо, що в цьому прикладі немає фактів про те, що Білл любить бейсбол. Щоб з'ясувати, чи любить Білл бейсбол, можна дати Прологу такий запит:

likes (bill, baseball).

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

likes (bill, Activity): - likes (torn, Activity).

Завантажте програму ch 02 e 01. Pro ​​в середу візуальної розробки Visual Prolog і запустіть її утилітою Test Goal.

predicates

likes (symbol, symbol)

clauses

likes (ellen, tennis).

likes (John, football).

likes (torn, baseball).

likes (eric, swimming).

likes (mark, tennis).

likes (bill, Activity): - likes (torn, Activity).

goal

likes (bill, baseball).

Утиліта Test Goal відповість у вікні програми:

yes (та)

Система використовувала комбіноване правило

likes (bill, Activity): - likes (torn, Activity).

з фактом

likes (torn, baseball). для вирішення, що likes (bill, baseball).

Спробуйте також наступний запит в GOAL-розділі:

likes (bill, tennis).

Утиліта Test Goal відповість:

no (немає)

оскільки:

  • немає фактів, які говорять, що Білл любить теніс;

  • ставлення Білла до тенісу не може бути логічно виведено з використанням даного правила і наявних у розпорядженні фактів.

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

7. ПРОГРАМИ НА VISUAL PROLOG

Синтаксис Visual Prolog розроблений для того, щоб відображати знання про властивості і взаємозв'язках.

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

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

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

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

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

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

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

Розділ clauses - це серце Visual Prolog-програми; саме в цей розділ записуються факти і правила, якими буде оперувати Visual Prolog, намагаючись вирішити мета програми.

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

Розділ domains служить для оголошення доменів, які не є стандартними доменами Visual Prolog.

В розділ goal поміщається мета Visual Prolog-програми.

9. Розділ пропозицій

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

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

10. Розділ предикатів

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

11. ОГОЛОШЕННЯ КОРИСТУВАЛЬНИЦЬКОГО Предикат

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

predicateName (argument_typel OptionalNamel,

argument_type2 OptionalName2, ...,

argument_typeN OptionalNameN)

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

Імена предикатів

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

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

Аргументи предикатів

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

12. Розділ доменів

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

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

Франк - чоловік, якому 45 років.

Використовуючи стандартні домени, ви можете так оголосити відповідний предикат:

person (symbol, symbol, integer).

У більшості випадків таке оголошення буде працювати добре, але не наочно для читання програми. Більш правильним було б наступне опис:

domains

name, sex = symbol

age = integer

predicates

person (name, sex, age)

Одним з головних переваг оголошення власних доменів є те, що Visual Prolog може відслідковувати помилки типів, наприклад, такі:

same_sex (X, Y): -

person (X, Sex, _),

person (Sex, Y, _).

Незважаючи на те, що і name і sex описуються як symbol, вони не еквівалентні один одному. Це і дозволяє Visual Prolog визначити помилку, якщо ви переплутаєте їх. Це корисно в тих випадках, коли ваші програми дуже великі і складні.

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

Наступний приклад програми при його завантаженні призведе до помилки типу.

Domains product, sum = integer

predicates

add_em_up (sum, sum, sum)

multiply_em (product, product, product)

clauses

add_em_up (X, Y, Sum):-Sum = X + Y.

multiply_em (X, Y, Product):-Product = X * Y.

Ця програма виконує дві операції: складає і примножує. Задамо їй наступну мету:

add _ em _ up (32, 54, Sum).

Visual Prolog (Test Goal) відповість:

Sum = 86

1 Solution

що є сумою двох цілих чисел, які ви передали в програму.

З іншого боку, ця ж програма за допомогою предиката multiply _ em примножує два аргументи. Припустимо, ми хочемо подвоїти твір 31 на 17. Задаємо наступну мету:

multiply _ em (31, 17, Sum), add _ em _ up (Sum, Sum, Answer).

і чекаємо, що Visual Prolog (Test Goal) відповість:

Sum = 527, Answer = 1054

1 Solution

Однак замість цього ви отримаєте помилку типу. Це сталося через те, що мала місце спроба передати результуюче значення предиката multiply _ em, яке відноситься до домену product, в якості першого і другого аргументів (які повинні належати до домену sum) в предикат add _ em _ up. І хоча обидва ці домену відповідають типу integer - це різні домени.

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

13. Розділ мети

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

  • за ключовим словом goal не слід: -;

  • при запуску програми Visual Prolog автоматично виконує мета.

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

14. Декларації та правила

У Visual Prolog є кілька вбудованих стандартних доменів. Їх можна використовувати при декларації типів аргументів предикатів без опису в розділі domains.

Основні стандартні домени перераховані в табл. 1.

Таблиця 1. Основні стандартні домени

Домен

Опис

Реалізація

short

Коротке, знакова, кількісне

Всі платформи 16 біт (-32 768-32 767)

ushort

Коротке, беззнаковое, кількісне

Всі платформи 16 біт (0-65 535)

long

Довге, знакова, кількісне

Всі платформи 32 біт (-2 147 483 648-2 147 483 647)

ulong

Довге, беззнаковое, кількісне

Всі платформи 32 біт (0-4 294 967 295)

integer

Знакова, кількісне, має платформо-залежний

Платформа 1 6 біт (-32 768-32 767)


розмір

Платформи 32 біт (-2 147 483 648-2 147 483 647)

unsigned

Беззнаковое, кількісне, має платформо-залежний розмір

Платформи 16 біт (0-65 535) Платформи 32 біт (0-4 294 967 295)

byte


Всі платформи 8 біт (0 - 55)

word


Всі платформи 16 біт (0-65 535)

dword


Всі платформи 32 біт (0-4 294 967 295)

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

Домени типів byte, word і dword найбільш зручні при роботі з машинними числами. В основному використовуються типи integer та unsigned, а також short і long (і їх беззнакові аналоги) для більш спеціалізованих додатків.

В оголошеннях доменів ключові слова signed і unsigned можуть використовуватися разом зі стандартними доменами типів byte, word і dword для побудови нових базових доменів. Так:

domains

i 8 = signed byte

створює новий базовий домен в діапазоні від -128 до +127.

Інші базові домени показані в табл. 2 1.

Таблиця 2. Основні стандартні домени

Домен

Опис і реалізація

char

Символ, реалізований як беззнакових byte. Синтаксично це символ, укладений між двома одиночними лапками: 'а'

real

Число з плаваючою комою, що реалізовується як 8 байт відповідно до угоди IEEE; еквівалентний типу double в С. При необхідності, цілі автоматично перетворюються у real

string

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

Приклади рядків:

telephone _ number "railway ticket" "Dorid Inc"

Рядки, які пишуться у програмі, можуть досягати довжини в 255 символів, у той час як рядки, які система Visual Prolog зчитує з файлу або будує всередині себе, можуть досягати (теоретично) до 4 Гбайт на 32-бітових платформах

symbol

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

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

Завдання типів аргументів при декларації предикатів

Оголошення доменів аргументів у роздiлi predicates називається завданням типів аргументів. Припустимо, є наступна зв'язок об'єктів:

Франк - чоловік, якому 45 років.

Факт Прологу, відповідний цієї пропозиції природної мови, може бути наступним:

person (frank, male, 45).

Для того щоб оголосити person (чоловік), як предикат з цими трьома аргументами, ви можете розмістити в розділі predicates наступний рядок:

person (symbol, symbol, unsigned).

Тут для всіх трьох аргументів використані стандартні домени. Відтепер кожен раз при роботі з предикатом person, ви повинні передавати йому три аргументи, причому перші два повинні бути типу symbol, а третій - типу integer.

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

Або, припустимо, що ви хочете описати предикат, який повідомляв би позицію букви в алфавіті, т. е. мета

alphabet _ position (Letter, Position)

повинна повернути вам Position = 1, якщо Letter = a, Position = 2, якщо Letter = b і т. д. Пропозиції цього предиката можуть виглядати наступним чином:

alphabet_position (A_character, N).

Якщо при оголошенні предиката використовуються тільки стандартні домени, то програмі не потрібен розділ domains. Припустимо, що ви хочете описати предикат так, що мета буде істинна, якщо A _ character є N-му символом алфавіту. Пропозиції цього предиката будуть такими:

alphabet _ position ('а', 1). alphabet _ position ('b', 2).

alphabet_position ('з', 3).

alphabet_position ('z1, 26).

Ви можете оголосити даний предикат наступним чином:

predicates

alphabet_position (char, unsigned)

і тоді вам не буде потрібен розділ domains. Якщо розмістити всі фрагменти програми разом, отримаємо:

predicates

alphabet_position (char, integer)

clauses

alphabet_position ('a', 1).

alphabet_position ('b', 2).

alphabet _ position ('c', 3).

% Тут знаходяться інші літери

alphabet _ position ('z', 26).

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

alphabet_position ('а', 1).

alphabet_position (X, 3).

alphabet_position ('z', What).

Арность (розмірність)

Арность предиката - це кількість аргументів, які він приймає. Ви можете мати два предиката з одним і тим же ім'ям, але відрізняється арності. У розділах predicates і clauses версії предикатів з одним ім'ям і різної арності повинні збиратися разом; за винятком цього обмеження, різна арность завжди розуміється як повне розходження предикатів. Проілюструємо це прикладом /

domains

person = symbol

predicates

father (person)% цей person - батько

father (person, person)% перший person є батьком іншого

clauses

father (Man):-father (Man, _).

father (adam, seth).

father (abraham, isaac).

Синтаксис правил

Правила використовуються в Пролозі в разі, коли який-небудь факт залежить від істинності іншого факту групи фактів. Як ми пояснювали раніше в цій главі, у правилі Прологу є дві частини: заголовок і тіло. Нижче представлений узагальнений синтаксис правила в Visual Prolog:

HEAD: - <Subgoal>, <Subgoal>, ..., <Subgoal>.

Тема: - <підцілі>, <підцілі>, ... , <Підцілі>.

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

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

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

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

якщо ЗАГОЛОВОК правдивий, тоді ТІЛО істинно (або: тоді виконати ТІЛО

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

ЗАГОЛОВОК правдивий, якщо ТІЛО - істинно (або: якщо ТІЛО може сить виконано).

Враховуючи вищесказане, правило Прологу відповідає умовній формі тодi / якщо (then / if).

Автоматичне перетворення типів

Зовсім не обов'язково, щоб при зіставленні двох Visual Prolog-змінних вони належали одному і тому ж домену. Змінні можуть бути пов'язані з константами з різних доменів. Таке (виборче) змішання допускається, оскільки Visual Prolog автоматично виконує перетворення типів (з одного домену в іншій), але тільки в наступних випадках:

  • між рядками (string) і ідентифікатори (symbol);

  • між цілими, дійсними і символами (char). При перетворенні символу в числове значення цим значенням є величина символу в коді ASCII.

Аргумент з домену my_dom, який оголошений таким чином:

domains

my_dom = <base domain>% <base domain> - це стандартний домен

може вільно змішуватися з аргументами з цього основного домену і з аргументами всіх сумісних з ним стандартних доменів. Якщо основний домен - string, то з ним сумісні аргументи з домену symbol; якщо ж основний домен integer, то з ним сумісні домени real, char, word та ін Таке перетворення типів означає, наприклад, що ви можете:

  • викликати предикат з аргументами на кшталт string, задаючи йому аргументи на кшталт symbol, і навпаки;

  • передавати предикату з аргументами на кшталт real параметри типу integer;

  • передавати предикату з аргументами на кшталт char параметри типу integer;

  • використовувати у виразах і порівняннях символи без необхідності отримання їх кодів в ASCII.

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

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

Тепер, коли ви ознайомилися з такими розділами програм Visual Prolog, як clauses, predicates, domains і goal, поговоримо про деякі інші, часто використовуваних розділах програм: facts, constants і різних глобальних (global) розділах.

Розділ фактів

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

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

Розділ констант

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

<I d> = <макроозначень>

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

Розглянемо наступний фрагмент програми:

constants

z е r о = Про

one = 1

two = 2

hundred = (10 * (10-1) +10)

pi = 3.141592653

ega = 3

slash_fill = 4

red = 4

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

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

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

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

  • це призведе до повідомлення про помилку "Recursion in constant definition "(Рекурсія в описі константи);

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

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

  • ідентифікатори констант є глобальними і можуть оголошуватися тільки один раз. Множинне оголошення одного і того ж ідентифікатора приведи до повідомлення про помилку "Constant identifier can only be declared once "(Ідентифікатор константи може оголошуватися тільки один раз).

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

Visual Prolog підтримує декілька директив компілятора, які можна додавати в програму для повідомлення компілятору спеціальних інструкцій з обробки вашої програми при її компіляції. Крім цього, ви можете встановлювати більшість директив компілятора з допомогою команди меню середовища візуальної розробки Visual Prolog Options / Project / Compiler Options.

Директива include

Для того щоб уникнути багаторазового набору повторюваних процедур, ви можете використовувати директиву include.

Нижче наведено приклад того, як це робиться.

  1. Створюєте файл (наприклад, MYSTUFF. PRO), в якому розкажете свої найбільш I часто використовувані предикати (за допомогою розділів domains і predicates) і даєте їх опис в розділі clauses.

  2. Пишете вихідний текст програми, яка буде використовувати ці процедури.

  3. У "допустимих областях" вихідного тексту програми розміщуєте рядок: include "mystuff. Pro"

"Допустимі області" - це будь-яке місце програми, в якому ви можете розташувати декларацію розділів domains, facts, predicates, clauses або goal.

При компіляції вихідних текстів програми Visual Prolog вставить зміст файлу MYSTUFF. PRO прямо в остаточний текст файлу для компіляції.

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

II. Уніфікація і пошук з поверненням

1. Зіставлення та уніфікація

Розглянемо програму ch 04 e 01. Pro ​​(рис.1) з точки зору того, як утиліта Test Goal буде відшукувати всі рішення наступної мети written_by (X, Y).

domains

title, author = symbol

pages = unsigned

predicates

book (title, pages)

written_by (author, title)

long_novel (title)

clauses

written_by (fle m ing, "DR NO").

written_by (melville, "MOBY DICK").

book ("MOBY DICK", 250).

book ("DR NO", 310).

long_novel (Title): -

written_by (_, Title),

book (Title, Length),

Length> 300.

  1. Лістинг програми ch04e01.pro

Намагаючись виконати цільове твердження written_by (X, Y), Visual Prolog повинен перевірити кожне речення written_by (X, Y) в програмі. Зіставляючи аргументи X і Y з аргументами кожної пропозиції written_by, Visual Prolog виконує пошук від початку програми до її кінця. Виявивши пропозицію, відповідне цільовим твердженням, Visual Prolog присвоює значення вільним змінним таким чином, що цільове твердження і пропозиція стають ідентичними. Кажуть, що цільове твердження уніфікується з пропозицією. Така операція зіставлення називається уніфікацією.

Оскільки X і Y є вільними змінними в цільовому затвердження, а вільна змінна може бути уніфікована з будь-яким іншим аргументом (і навіть з іншої вільної змінної), то цільове твердження може бути уніфіковано з першою пропозицією written _ by у програмі, як показано нижче:

written_by (X, Y).

¯ ¯

written_by (fleming, "DR NO").

Visual Prolog встановлює відповідність, X стає пов'язаним з fleming, a Y - "dr no ". У цей момент Visual Prolog надрукує:

X = fleming, Y = "DR NO"

Оскільки Test Goal шукає всі рішення для заданої мети, цільове твердження також буде уніфіковано і з другим реченням written _ by:

written_by (melville, "MOBY DICK").

Test Goal друкує друге рішення:

X = melville, Y = "MOBY DICK"

2 Solutions

Розглянемо, як Visual Prolog виконає наступне цільове твердження:

long_novel (X).

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

long_novel (Title)

Visual Prolog перевіряє пропозиція для long _ novel, намагаючись завершити зіставлення уніфікацією аргументів. Оскільки в цільовому затвердження X - вільна змінна, то вона може бути уніфікована з будь-яким іншим аргументом. Title також не є пов'язаним у заголовку пропозиції long _ novel. Цільове твердження відповідає заголовку правила, і уніфікація виконується. Згодом Visual Prolog буде намагатися погоджувати підцілі за правилом

long_novel (Title): -

written_by (_, Title), book (Title, Length), Length> 300.

Намагаючись виконати узгодження тіла правила, Visual Prolog звернеться до першої підцілі в тілі правила - written _ by (_, Title). Оскільки авторство книги є несуттєвим, на місці аргументу author з'являється анонімна змінна (_). Звернення written _ by (_, Title) стає поточною підцілі, і Пролог шукає рішення для цього звернення.

Пролог шукає відповідність з даною підцілі від вершини і до кінця програми. У результаті досягається уніфікація з першим фактом для written _ by, а саме:

written_by (_, Title),

¯ ¯

written_by (fleming, "DR NO").

Змінна Title пов'язується з "dr no ", і до наступної підцілі book (Title, Length) звернення виконується вже з цим значенням змінної. Далі Visual Prolog починає черговий процес пошуку, намагаючись знайти відповідність із зверненням до book. Так як Title пов'язаний з "dr no ", фактичне звернення виглядає як book (" DR NO ", Length). Процес пошуку знову починається з вершини програми. Зауважимо, що перша спроба зіставлення з пропозицією book (" MOBY DICK ", 250) завершиться невдало, і Visual Prolog перейде до другого пропозицією book в пошуку відповідності. Тут заголовок книги відповідає підцілі, і Visual Prolog пов'язує змінну Length з величиною 310.

Тепер третє речення в тілі long _ novel стає поточною підцілі:

length> 300.

Visual Prolog виконує порівняння, що завершується успішно: 310 більше, ніж 300. У цей момент всі підцілі в тілі правила виконані, і, отже, звернення long _ novel (X) успішно. Так як X у зверненні був уніфікований зі змінною Title в правилі, то значення, з яким пов'язується Title при підтвердженні правила, повертається і уніфікується зі змінною X. Змінна Title у разі підтвердження правила має значення "dr no ", тому Visual Prolog виведе:

X = "DR NO"

1 Solution.

2. Пошук з поверненням

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

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

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

predicates

likes (symbol, symbol)

tastes (symbol, symbol)

food (symbol)

clauses

likes (bill, X): -

food (X), tastes (X, good).

tastes (pizza, good).

tastes (brussels_sprouts, bad).

food (brussels_sprouts).

food (pizza).

  1. Програма ch04e02.pro

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

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

likes (bill, What).

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

У даному випадку Пролог буде шукати рішення, виробляючи з вершини програми пошук відповідності з підцілі likes (bill, what).

Він виявляє відповідність з першою пропозицією в програмі і мінлива What уніфікується зі змінною X. Зіставлення із заголовком правила змушує Visual Prolog спробувати задовольнити це правило. Виробляючи це, він рухається по тілу правила і звертається до першої знаходиться тут підцілі: food (X).

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

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

Він виявляє відповідність із запитом у першого ж факту, що представляє ставлення food. Таким чином, змінна X пов'язується зі значенням brussels _ sprouts. Оскільки існує більш ніж один можливий відповідь на звернення food (X), Visual Prolog ставить точку повернення (маркер) біля факту food (brussels _ sprouts). Ця точка пошуку з поверненням вказує на те місце, звідки Пролог почне пошук наступного можливого відповідності для food (X).

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

Оскільки змінна X пов'язана з brussels _ sprouts, наступне звернення буде виконуватися так:

tastes (brussels_sprouts, good)

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

food (brussels_sprouts).

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

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

Звернення було food (X), так що зв'язаність brussels _ sprouts з X скасована. Тепер Пролог намагається заново провести рішення для цього звернення. Він виявляє відповідність з фактом food (pizza); на цей раз змінна X пов'язується зі значенням pizza.

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

Оскільки мінлива what в цільовому затвердження уніфікована з змінної X у правилі likes, а змінна X пов'язана зі значенням pizza, мінлива What відтепер пов'язана зі значенням pizza і Visual Prolog повідомляє рішення:

What = pizza

1 Solution

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

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

Visual Prolog забезпечує два інструментальні засоби, які дають можливість управляти механізмом пошуку з поверненням: предикат fail, який використовується для ініціалізації пошуку з поверненням, і cut або відсікання (позначається!) - Для заборони можливості повернення.

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

Visual Prolog починає пошук з поверненням, коли виклик завершується невдало. У певних ситуаціях буває необхідно ініціалізувати виконання пошуку з поверненням, щоб знайти інші рішення. Visual Prolog підтримує спеціальний предикат fail, викликає неуспішної завершення, і, отже, ініціалізує повернення. Дія предиката fail рівносильно ефекту від порівняння 2 = 3 або інший неможливою підцілі. Програма ch 04 e 06. Pro ​​(рис. 3) ілюструє використання цього спеціального предиката.

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 \ n"), fail.

  1. Програма ch04e06.pro

Нехай необхідно знайти всі рішення мети father (X, Y). Використовуючи утиліту Test Goal, можна записати мету як

goal

father (X, Y).

Test Goal знайде всі рішення мети father (X, Y) і відобразить значення всіх змінних наступним чином:

X = leonard, Y = katherine

X = carl, Y = jason

X = carl, Y = marilyn

3 Solutions

Але якщо ви скомпілюєте цю програму і запустіть її, то Visual Prolog знайде тільки перше відповідне рішення для father (X, Y). Після того як цільове твердження, визначене в розділі goal, виконано вперше, ніщо не говорить Прологу про необхідність продовження пошуку з поверненням. Тому звернення до father призведе тільки до одного рішення. Як же знайти всі можливі рішення? Предикат everybody у програмі ch 04 e 06. Pro ​​використовує fail для підтримки пошуку з поверненням.

Завдання предиката everybody - знайти всі рішення для father і видати повну відповідь. Порівняйте попередні відповіді утиліти Test Goal з метою father (X, Y) і відповіді на виконання наступної мети:

goal

everybody.

відображені згенерованої програмою:

leonard is katherine 's father

carl is Jason's father

carl is marilyn's father

Предикат everybody використовує пошук з поверненням з тим, щоб отримати всі рішення для father (X, Y), змушуючи Пролог виконувати пошук з поверненням крізь тіло правила everybody:

father (X, Y),

mite (X, "is", Y, "'s father \ n"),

fail.

fail не може бути погоджений (він завжди неуспешен), тому Visual Prolog змушений повторювати пошук з поверненням. При пошуку з поверненням він повертається до останнього зверненням, яке може призвести множинні рішення. Таке звернення називають недетермінованим. Недетермінірованние звернення є протилежністю детермінованому зверненням, яке може зробити тільки одне рішення.

Предикат write не може бути знову узгоджений (він не може запропонувати нових рішень), тому Visual Prolog повинен виконати відкат далі, на цей раз до першої підцілі в правилі.

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

Переривання пошуку з поверненням: відсікання

Visual Prolog передбачає можливість відсікання, яка використовується для переривання пошуку з поверненням; відсікання позначається знаком оклику (!). Діє відсікання просто: через нього неможливо зробити відкат (пошук з поверненням).

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

Існують два основні випадки застосування відсікання.

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

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

У цьому питанні даються приклади, що показують, як слід використовувати відсікання, розглядаються декілька умовних правил (rl, r 2 і r З), які визначають умовний предикат р, а також кілька підцілей - а, b, с і т. д.

      1. Запобігання пошуку з поверненням до попередньої підцілі у правилі

r1: - а, b,

!,

c.

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

В якості конкретного прикладу розглянемо програму ch 04 e 07. Pro ​​(рис. 4).

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).

goal

buy_car (corvette, Y).

  1. Рис. 4. Програма ch04e07.pro

У даному прикладі поставлена ​​мета: знайти corvette (Корвет) приємного кольору, відповідний по вартості. Відсікання в правилі buy _ car означає, що оскільки в базі даних є тільки один "Корвет" приємного кольору, хоч і з дуже високою ціною, то немає потреби шукати іншу машину. Отримавши цільове твердження

buy_car (corvette, Y)

програма відпрацює наступні кроки:

1. Visual Prolog звертається до саг, першою підцілі для предиката buy _ car.

2. Виконує перевірку для першої машини, maserati, яка завершується невдало.

3. Потім перевіряє наступну пропозицію саг і знаходить відповідність, пов'язуючи змінну Color зі значенням black.

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

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

6. Знаходить відповідність і знову перевіряє колір. На цей раз колір виявляється приємним, і Visual Prolog переходить до наступної підцілі у правилі: до відсікання. Відсікання негайно виконується, "заморожуючи" всі змінні, раніше пов'язані в цьому реченні.

7. Переходить до наступної (і останньої) підцілі в правилі, до порівняння

Price <25000.

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

      1. Запобігання пошуку з поверненням до наступного речення

Відсікання може бути використано, як спосіб повідомити Visual Prolog, що він вибрав вірне пропозиція для певного предиката. Наприклад, розглянемо наступний фрагмент:

r (1): -

!,

а, b, с.

r (2): -

!,

d.

r (3): -

!,

с.

r (_): -

write ("This is a catchall clause.").

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

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

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

Детермінізм і відсікання

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

У Пролозі існує директива компілятора check _ determ. Якщо вставити цю директиву в самий початок програми, то Visual Prolog буде видавати попередження в разі виявлення недетермінованих пропозицій в процесі компіляції.

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

Предикат not

Наступна програма ch 04 el 0. Pro ​​(рис. 5.) Демонструє, як ви можете використовувати предикат not для того, щоб виявити встигає студента: студента, у якого середній бал (GPA) не менше 3.5 і у якого в даний час не продовжується випробувальний термін.

domains

name = symbol

gpa = real

predicates

honor_student (name)

student (name, gра)

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").

goal

honor_student (X).

  1. Програма ch04e10.pro

При використанні предиката not необхідно мати на увазі наступне:

Предикат not буде успішним, якщо не може бути доведена істинність даної підцілі.

Це призводить до запобігання зв'язування всередині not незв'язаних змінних. При виклику зсередини not підцілі з вільними змінними, Visual Prolog поверне повідомлення про помилку: "Free variables not allowed in not or retractall "(Вільні змінні не дозволені у not або retract). Це відбувається внаслідок того, що для зв'язування вільних змінних в підцілі, підцілі повинна уніфікуватися з яким-небудь іншим пропозицією і виконуватися. Правильним способом управління непов'язаними змінними підцілі всередині not є використання анонімних змінних .

Перший приклад працює правильно:

likes (bill, Anyone): -% Anyone - вихідний аргумент

likes (sue, Anyone),

not (hates (bill, Anyone).

У цьому прикладі Anyone зв'язується за допомогою likes (sue, Anyone) до того, як Visual Prolog робить висновок, що hates (bill, Anyone) не є істиною. Дана пропозиція працює коректно.

Якщо приклад змінити таким чином, що звернення до not буде виконуватися першим, то отримаєте повідомлення про помилку: "Free variable are not allowed in not "(Вільні змінні в not не дозволені).

likes (bill, Anyone): -% Це не буде працювати правильно

not (hates (bill, Anyone)),

likes (sue, Anyone).

Навіть якщо ви заміните в not (hates (bill, Anyone)) Anyone на анонімну змінну, і пропозиція, таким чином, не буде повертати помилку, все одно отримаєте неправильний результат.

likes (bill, Anyone): -% Це не буде працювати правильно

not (hates (bill, _)),

likes (sue, Anyone).

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

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

До цих пір ми працювали тільки основними видами об'єктів даних Visual Prolog, таких як числа, ідентифікатори і рядки. Visual Prolog може створювати не тільки прості, але і складові типи.

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

Простий об'єкт даних - це змінна або константа. Не плутайте це значення слова "константа" з символьними константами, які ви визначаєте в розділі constants програми. Те, що ми тут називаємо константою, це щось, що її ідентифікує об'єкт, який не можна змінювати: символ (char), число (integer або real) або атом (symbol або string).

Константи включають числа, символи і атоми. Числа та символи були розглянуті раніше.

Атоми мають тип ідентифікатор (symbol) або рядок (string). Відмінність між ними - головним чином питання машинного подання та реалізації, і, в основному, воно синтаксично не помітно. Коли атом приймає в якості аргументу при виклику предиката, то до якого домену належить атом - symbol або string-визначається по тому, як описано цей аргумент у декларації предиката.

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

Атоми типу string виділяються подвійними лапками і можуть містити будь-яку комбінацію літер, крім ASCII-нуля (0, бінарний нуль), який позначає кінець рядка атома.

Приклади рядків і ідентифікаторів наведено в табл. 1.

  1. Рядки і ідентифікатори

Атоми-ідентифікатори

Атоми-рядки

food

"Jesse James"

rick _ Jones _2nd

"123 Pike street"

fred _ Flintstone _1000_ B с_ Bedrock

"Jon"

a

"A"

new _ york

"New York"

pdcProlog

"Visual Prolog, by Prolog Development Center"

Так як string / symbol взаємозамінні, їх відмінність не істотно. Проте імена предикатів і функтори для складених об'єктів повинні відповідати синтаксичним угодами домену symbol.

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

Складні об'єкти даних дозволяють інтерпретувати деякі частини інформації як єдине ціле таким чином, щоб потім можна було легко розділити їх знову. Візьмемо, наприклад, дату "15 жовтня 1991". Вона складається з трьох частин інформації - місяць, день і рік. Уявімо її на рис. 1, як деревоподібну структуру.

  1. Деревоподібна структура дати

Можна оголосити домен, що містить складовою об'єкт date:

domains

date_cmp = date (string, unsigned, unsigned)

а потім просто записати:

D = date ("0ctober", 15,1991).

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

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

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

Рис. 2. деревоподібна структура дати народження.

На мовою Пролог це виглядає наступним чином:

birthday (person ("Leo", "Jensen"), date ("Apr", 14,1960))

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

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

date ("April", 14, I960)

зіставляється з X і привласнює X значення date ("April", 14,1960). Також

date ("April", 14, I960)

зіставляється з date (Mo, Da, Yr) і присвоює змінним Мо = "April", Da = 14 і Yr = 1960.

  1. Використання декількох значень як єдиного цілого

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

owns (john, book ("From Here to Eternity", "James Jones")).

в якому стверджується, що у Джона є книга "From Here to Eternity "(Звідси у вічність), написана James Jones (Джеймсом Джонсом). Аналогічно можна записати:

owns (john, horse (blacky)).

що означає:

John owns a horse named blacky. (У Джона є кінь Блекі.)

Якщо замість цього описати лише два факти:

owns (john, "From Here to Eternity"), owns (john, blacky).

то не можна було б визначити, чи є blacky назвою книги або ім'ям коні.

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

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

owns (john, book ("From Here to Eternity", "James Jones")).

і

owns (John, horse (blacky)).

ви можете надіслати системі запит в наступному вигляді:

owns (John, X)

Змінна Х може бути пов'язана з різними типами об'єктів: книга, коня і, можливо, іншими об'єктами, які ви визначите. Відзначимо, що тепер ви не можете більше використовувати старе визначення предиката owns:

owns (symbol, symbol)

Другий елемент більш не є об'єктом типу symbol. Замість цього ви можете дати нове визначення цього предиката

owns (name, articles)

Домен articles в розділі domains можна описати так

domains

articles = book (title, author); horse (name)

Крапка з комою читається як "або" У цьому випадку можливі два варіанти книга буде визначатися своїм заголовком і автором, а кінь буде розпізнаватися своїм ім'ям Домени title, author і name мають стандартний тип symbol.

До визначення домену легко можуть бути додані інші варіанти.

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

Visual Prolog дозволяє конструювати складені об'єкти на кількох рівнях. Наприклад:

domains

articles = book (title, author);% Перший рівень

author = author (first_name, last_name)% Другий рівень

title, first_name, last_name = symbol% ​​Третій рівень

При використанні складових об'єктів з багатьма рівнями часто допомагає таке "дерево" (рис. 7):

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

Повторення та рекурсія

Комп'ютери здатні повторювати одне і те ж дію знову і знову, Visual Prolog може висловлювати повторення як в процедурах, так і в структурах даних. Ідея повторюваних структур даних може здатися дивною, але Пролог дозволяє створювати структури даних, розмір яких не відомий під час створення.

  1. Процес повторення

Програмісти на мовах Pascal, Basic або С, які починають використовувати Visual Prolog, часто відчувають розчарування, виявивши, що мова не має конструкцій for, while або repeat. У Пролозі не існує прямого способу вираження повтору. Пролог забезпечує тільки два види повторення

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

  • і рекурсію, в якій процедура викликає сама себе.

Однак цей недолік не знижує мощі Прологу. Фактично, Visual Prolog розпізнає спеціальний випадок рекурсії - хвостову рекурсію - і компілює її в оптимізовану итерационную петлю. Це означає, що хоча програмна логіка і виражається рекурсивно, скомпільований код так само ефективний, як якщо б програма була написана на Pascal або Basic.

Використання пошуку з поверненням для організації повторів

Коли виконується процедура пошуку з поверненням (відкинути), відбувається пошук іншого рішення цільового затвердження. Це здійснюється шляхом повернення до останньої з перевірених підцілей, що має альтернативне рішення, використання наступної альтернативи цій підцілі та нової спроби руху вперед (див. приклад ch 06 e 01). Дуже часто для цього використовується директива fail.

predicates

country (symbol)

print_countries

clauses

country ("England").

country ("France").

country ("Germany").

country ("Denmark").

print_countries: -

country (X),

write (X),% записати значення Х

nl,% розпочати новий рядок

fail.

print_countries.

goal

print__countnes.

  1. Програма ch06e01.pro

Попередні і наступні операції

Відзначимо, що програма, яка знаходить рішення для цільового затвердження, може виконувати будь-які попередні або завершальні операції. Наприклад, у нашому прикладі програма могла б:

  1. Надрукувати

Some delightful places to live are ... (Деякі чудові місця для проживання ...).

  1. Надрукувати всі рішення для country (X).

  2. Завершити друк фразою And maybe others (Можуть бути й інші).

Зауважте, що print _ countries, визначене в попередньому прикладі, вже містить пропозицію вивести на друк всі рішення country (X) і віддрукувати завершальне повідомлення.

Перша пропозиція для print _ countries відповідає кроку 2 і виводить на друк всі рішення. Його друге речення відповідає кроку 3 та просто успішно завершує цільове твердження (тому що перше речення завжди в режимі fail - "невдале завершення").

Можна було б змінити друге речення у програмі ch 06 e 01. Pro.

print_countnes: -

write ("And maybe others."), nl.

яка виконала б крок 3, як зазначено.

А що можна сказати про крок 1? У ньому немає сенсу, коли print _ countnes містив лише 2 пропозиції. Але в предикаті може бути і три пропозиції:

print_countries: -

write ("Some delightful places to live are"), nl,

fail.

pnnt_countnes: -

country (X),

write (X), nl,

fail.

print_countries: -

write ("And maybe others."), nl.

Наявність fail в першому реченні важливо, оскільки він забезпечує після виконання першого речення повернення і перехід до другого пропозицією Крім того, це важливо, тому що предикати write і nl не утворюють альтернатив Строго кажучи, перше речення перевіряє всі можливі рішення перед тим, як завершитися неуспіхом .

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

Використання відкоту з петлями

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

repeat

repeat - repeat

Цей прийом демонструє створення структури управління Прологу (см лістинг на рис. 2.), Яка породжує нескінченну безліч рішень. Мета предиката repeat - допустити нескінченність пошуку з поверненням (нескінченну кількість відкатів)

/ * Використання repeat для збереження введених символів і друкувати їх до тих пір, поки користувач не натисне Enter (Введення) * /

predicates

repeat

typewriter

clauses

repeat.

repeat-repeat.

typewriter: -

repeat,

readchar (C),% Читати символ, його значення привласнити З

write (С),

З = '\ r',% Символ повернення каретки (Enter)? або неуспіх

goal

typewriter (), nl.

  1. Лістинг 13.2. Програма ch06e02.pro

Програма ch06e02 pro показує, як працює repeat Правило typewriter - описує процес прийому символів з ​​клавіатури і відображення їх на екрані, поки користувач не натисне клавішу <Enter> (<Return>)

Правило typewriter працює наступним чином

1 Виконує repeat (який нічого не робить, але ставить крапку відкоту).

2 Привласнює змінної з значення символу.

3 Відображає С.

4 Перевіряє, чи відповідає з кодом повернення каретки.

5 Якщо відповідає, то - завершення. Якщо ні - повертається до точки відкоту і шукає альтернативи, тому що ні write, ні readchar не є альтернативами,

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

Поняття рекурсії

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

Логіка рекурсії проста для здійснення. Уявіть собі ЕОМ, здатну "зрозуміти":

Знайти факторіал числа N:

Якщо N дорівнює 1, то факторіал дорівнює 1

Інакше знайти факторіал N-1 і помножити його на N.

Цей підхід означає наступне:

перше («закручуєте» стек), щоб знайти факторіал 3, ви повинні знайти факторіал 2, а щоб знайти факторіал 2, ви повинні обчислити факторіал 1. факторіал 1 шукається без звернення до інших факторіалом, тому що він дорівнює 1, тому повторення не почнуться.

друге («розкручуєте» стек), якщо у вас є факторіал 1, то множте його на 2, щоб отримати факторіал 2, а потім множите отримане на 3, щоб отримати факторіал 3.

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

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

Рекурсія має три основні переваги:

  • вона може висловлювати алгоритми, які не можна зручно виразити ніяким іншим чином;

  • вона логічно простіше методу ітерації;

  • вона широко використовується в обробці списків.

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

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

Приклад рекурсивного визначення правил

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

визначати безпосередніх (найближчих) предків, а друге - віддалених. Будемо говорити, що деякий X є віддаленим предком деякого Z, якщо між X і Z існує ланцюжок людей, пов'язаних між собою ставленням батько-дитина, як показано на рис.1 .. У нашому прикладі на рис. 1. Том - найближчий предок Ліз і віддалений предок Пат.

  1. Приклад відносини предок: (а) X - найближчий предок Z; (b) X - віддалений предок Z.

Перше правило просте і його можна сформулювати так:

Для всіх X і Z,

X - предок Z, якщо X - батько Z.

Це безпосередньо перекладається на Пролог як

предок (X, Z): .- батько (X, Z).

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

предок (X, Z): -

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

предок (X, Z): -

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

предок (X, Z): -

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

батько (Y1, Y2),

батько (Y2, Z).

предок (X, Z): -

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

батько (Y1, Y2),

батько (Y2, Y3),

батько (Y3, Z).

  1. Пари предок-нащадок, розділених різним числом поколінь.

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

Існує, однак, коректна й елегантна формулювання відносини предок - коректна в тому сенсі, що буде працювати для предків довільній віддаленості. Ключова ідея тут - визначити ставлення предок через нього самого. Рис. 3 ілюструє цю ідею:

Для всіх X і Z,

X - предок Z, якщо існує Y, такий, що

(1) X - батько Y і

(2) Y - предок Z.

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

предок (X, Z): -

батько (X, Y), предок (Y, Z).

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

предок (X, Z): -

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

предок (X, Z): -

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

предок (Y, Z).


Рекурсивна формулювання відносини предок.

Ключовим моментом в даній формулюванні було використання самого відношення предок у його визначенні. Такі визначення називаються рекурсивними. Логічно вони абсолютно коректні і зрозумілі. Рекурсія - один з фундаментальних прийомів програмування на Пролозі. Без рекурсії з його допомогою неможливо вирішувати завдання скільки-небудь відчутною складності.

Оптимізація хвостової рекурсії

У рекурсії є один великий недолік - вона «з'їдає» пам'ять. Кожного разу, коли одна процедура викликає іншу, інформація про виконання викликає процедури повинна бути збережена для того, щоб вона (кричуща процедура) могла, після виконання викликаною процедури, відновити виконання на тому ж місці, де зупинилася. Це означає, що якщо процедура викликає себе 100 разів, то 100 різних станів повинно бути записано одночасно (стану виконання рішення зберігаються в стекової фреймі). Максимальний розмір стека у 16-бітових платформ, таких як IBM PC, що працює під DOS, становить 64 Кбайт , що дозволяє розмістити максимум 3000 або 4000 стекових фреймів. На 32-бітних платформах стек теоретично може зрости до декількох гігабайт; але тут виявляться інші системні обмеження, перш ніж стік переповниться. Що ж можна зробити, щоб уникнути використання такого великого стекового простору?

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

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

Наприклад, припустимо, що процедура А викликає процедуру В, а В - С в якості свого останнього кроку. Коли В викликає С, В не повинна більше нічого робити. Тому, замість того щоб зберегти в стеку процедури До інформації про поточний стан С, ми можемо переписати стару збережену інформацію про стан В (яка більше не потрібна) на поточну інформацію про С, зробивши відповідні зміни до інформації, що зберігається. Коли З закінчить виконання, вона буде вважати, що вона викликана безпосередньо процедурою А.

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

Ця операція називається оптимізацією хвостової рекурсії (tail recursion optimization) або оптимізацією останнього дзвінка (last - call optimization) Зверніть увагу, що з технічних причин оптимізація останнього дзвінка незастосовна до рекурсивним функцій.

Як задати хвостову рекурсію

Що означає фраза "одна процедура викликає іншу, виконуючи свої самий останній крок"? На мовою Пролог це означає.

П виклик є самої останньої підцілі пропозиції,

Про раніше в пропозиції не було точок повернення

Нижче наводиться задовольняє обом умовам приклад

count (N): - write (N), nl, NewN = N + l, count (NewN).

Ця процедура є хвостовій рекурсією, яка викликає себе без резервування нового стекового фрейму, і тому не виснажує запас пам'яті Як показує програма ch 06 e 04 pro (лістинг 13 квітня), якщо ви дасте їй цільове твердження

count (0).

то предикат count буде друкувати цілі числа, починаючи з 0, і ніколи не зупиниться У кінцевому рахунку відбудеться цілочисельне переповнення, але зупинки через виснаження пам'яті не відбудеться

Лістинг 13.4. Програма ch 06 e 04. Pro

/ * Програма з хвостової рекурсією, яка не виснажує пам'ять * / predicates count (ulong)

clauses

count (N): -

write ('\ r', N), NewN = N + l, count (NewN).

GOAL nl, count (0).

  1. Визначення списку

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

Список, що містить числа 1, 2 і 3, записується так:

[1, 2, 3]

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

[Dog, cat, canary]

["Valerie ann", "jennifer caitlin", "benjamin thomas"]

  1. Оголошення списків

Щоб оголосити домен для списку цілих, треба використовувати декларацію домену, таку як:

domains

integerlist = integer *

Символ (*) означає "список чого-небудь"; таким чином, integer * означає "список цілих".

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

domains

elementlist = elements *

elements = ....

Тут elements мають єдиний тип (наприклад: integer, real чи symbol) або є набором відмінних один від одного елементів, зазначених різними функторами. У Visual Prolog не можна змішувати стандартні типи в списку. Наприклад, наступна декларація неправильно визначає список, складений з елементів, що є цілими і дійсними числами або ідентифікаторами:

elementlist = elements *

elements = integer; real; symbol / * Невірно * /

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

elementlist = elements *

elements = i (integer); r (real); s (symbol)% функтори тут i, r і s

  1. Голови і хвости

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

голова [а, b, с] є а

хвіст [а, b, с] є [b, с]

Що відбувається, коли ви доходите до одноелементної списку? Відповідь така:

голова [з] є з

хвіст [з] є []

Якщо вибирати перший елемент списку достатню кількість разів, ви обов'язково дійдете до порожнього списку []. Порожній список не можна розділити на голову і хвіст.

У концептуальному плані це означає, що список має структуру дерева, як і інші складові об'єкти. Структура дерева [а, b, с, d] представлена ​​на рис. 1.

Рис. 1. Структура дерева

Одноелементні список, як, наприклад [а], не те ж саме, що елемент, який до нього входить, тому що [а] насправді - це складова структура даних.

  1. Робота зі списками

У Пролозі є спосіб явно відділити голову від хвоста. Замість поділу елементів комами, це можна зробити вертикальної рисою "|". Наприклад:

[А, b, с] еквівалентно [а | [b, с]] і, продовжуючи процес,

[А | [b, с]] еквівалентно [а | [b | [з]]], що еквівалентно [а | [b | [з | []]]]

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

[А, b, с, d] як [а, b | [с, d]].

У табл. 1. наведено кілька прикладів на привласнення в списках.

Таблиця 1. Присвоєння в списках

Список 1

Список 2

Присвоєння змінним

[X, Y, Z]

[Егберт, їсть, морозиво]

Х = егберг, У = їсть, Z = морозиво


[7]

[X | Y]

Х = 7, Y = []

[1, 2, 3, 4]

[X, Y | Z]

X = l, Y = 2, Z = [3,4]

[1, 2]

[3 | X]

fail% невдача


  1. Використання списків

Список є рекурсивної складовою структурою даних, тому потрібні алгоритми для його обробки. Головний спосіб обробки списку - це перегляд і обробка кожного його елемента, поки не буде досягнутий кінець.

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

  1. Друк списків

Якщо потрібно надрукувати елементи списку, це робиться так, як показано в лістингу 1.

Лістинг 1. Програма ch 07 e 01. Pro;

domains

list = integer *% Або будь-який тип, який ви хочете

predicates

write_a_list (list)

clauses

write_a_list ([]),% Якщо список порожній - нічого не робити

write_a_list ([Н | Т ]):-% Присвоїти Н-голова, Т-хвіст, після чого ...

write (H), nl,

write_a_list (Т).

goal

write_a_list ([1, 2, 3]).

Ось два цільових затвердження write _ a _ list, описані на звичайній мові:

Друкувати порожній список - значить нічого не робити.

Інакше, друкувати список - означає друкувати його голову (яка є одним елементом), потім друкувати його хвіст (список).

  1. Підрахунок елементів списку

Розглянемо, як можна визначити число елементів у списку. Що таке довжина списку? Ось просте логічне визначення:

Довжина [] - 0.

Довжина будь-якого іншого списку - 1 плюс довжина його хвоста.

Чи можна застосувати це? У Пролозі - так. Для цього потрібні дві пропозиції (лістинг 2).

Лістинг 2. Програма ch07e02.pro

domains

list = integer *

predicates

length_of (list, integer)

clauses

length_of ([], 0).

length_of ([_ | T], L): -

length_of (T, TailLength),

L = TailLength + 1.

Подивимося спочатку на друге речення. Дійсно, [_ | T] можна зіставити будь-якого непорожній списком, з присвоєнням т хвоста списку. Значення голови не важливо, головне, що воно є, і комп'ютер може порахувати його за один елемент.

Таким чином, цільове твердження

length_of ([1, 2, 3], L).

підходить друге пропозиції при T = [2, 3]. Наступним кроком буде підрахунок довжини T. Коли це буде зроблено (не важливо як), TailLength буде мати значення 2, і комп'ютер додасть до нього 1, а потім привласнить L значення 3.

Отже, як комп'ютер виконає проміжний крок? Це крок, в якому визначається довжина [2, 3] при виконанні цільового затвердження

length_of ([2, 3], TailLength).

Іншими словами, length _ of викликає сама себе рекурсивно.

1 Маються й інші стандартні домени.


Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Лекція
302.4кб. | скачати


Схожі роботи:
Мова програмування Visual Basic for Applications
Мова програмування C та середовище розробки Microsoft Visual C
Мова програмування C та середовище розробки Microsoft Visual C
Табличний процесор MS Excel Мова програмування Visual Basic for Applications
Логічні задачі на мові програмування Prolog
Програмування на Visual Basic
Завдання з програмування на Visual Basic
Створення програмного продукту на мові програмування Visual Basic for Applications
Access і Visual basic for Application Excel VBA прийоми програмування
© Усі права захищені
написати до нас