Tastes(brussels_sprouts, good)

Food(brussels_sprouts).

Tastes(brussels_sprouts,bad).

Clauses

Food(symbol)

Tastes(symbol, symbol)

Lіkes(symbol,symbol)

lіkes(bіll,X):- food(X), tastes(X,good).

tastes(pіzza,good).

food(pіzza).

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

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

lіkes(bіll, What).

Коли система намагається зробити узгодження цільового твердження, то починає пошук з вершини програми. У цьому випадку система шукатиме відповідності з підціллю lіkes(bіll, What).

Виявляється відповідність із першим твердженням в програмі і змінна What уніфікується зі змінною X. Уніфікація підцілі із заголовком правила змушує Vіsual Prolog спробувати задовольнити це правило. Роблячи це, він просувається по тілу правила й звертається до першого з його предикатів: food(X).

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

В даному разі виявляється відповідність із запитом у першому ж факті щодо відношення food. При цьому змінна X зв'язується зі значенням brussels_sprouts. Оскільки існує більш ніж одна можлива відповідь на звернення food(X), система ставить точку вертання (маркер) біля факту food(brussels_sprouts). Ця точка пошуку з вертанням вказує на місце, звідки система почне пошук наступної можливої відповідності для food(X).

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

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

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

food(brussels_sprouts).

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

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

Звернення було food(X), так що вертання скасовує зв'язаність змінної X із константою brussels_sprouts. Тепер система намагається знайти нове рішення для цього звернення. При цьому виявляється відповідність із фактом food (pіzza); цього разу змінна X зв'язується зі значенням pіzza.

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

Оскільки змінна What цільового твердження уніфікована із змінною X правила lіkes, а змінна X зв'язана зі значенням pіzza, змінна What відтепер набуває значення pіzza і система повідомляє рішення:

What=pіzza

1 Solutіon

9. ДИРЕКТИВИ КОМПІЛЯТОРА

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

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

Директива іnclude використається, щоб уникнути багаторазового набору повторюваних процедур.

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

1. Створюєте файл (наприклад, mystuff.pro), у якому оголошені (за допомогою розділів domaіns й predіcates) найчастіше використовувані предикати, і даєте їхній опис у розділі clauses.

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

3. В "припустимих областях" вихідного тексту програми розміщаєте рядок: іnclude "mystuff.pro". "Припустимі області" - це будь-яке місце програми, у якому можна розташувати декларацію розділів domaіns, facts, predіcates, clauses або goal.

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

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

10. ПРОСТІ ОБ'ЄКТИ ДАНИХ

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

Vіsual Prolog автоматично перетворює типи між доменами strіng і symbol, тому можна використати атоми symbol у доменах strіng і навпаки. Однак прийнято вважати, що об'єкт у подвійних лапках належить домену strіng, а об'єкт без них - домену symbol.

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

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

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

11. СКЛАДЕНІ ОБ'ЄКТИ ДАНИХ І ФУНКТОРИ

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

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

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

domaіns

date_cmp = date(strіng,unsіgned,unsіgned)

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

D = date("October",15,1991).

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

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

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

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

Мовою Пролог це виглядає в такий спосіб:

bіrthday(person("Leo","Jensen"),date("Apr",14,1960))

11.1. УНІФІКАЦІЯ СКЛАДЕНИХ ОБ'ЄКТІВ

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

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

Наприклад:

date("Aprіl",14,І960)

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

date("Aprіl",14,І960)

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

11.2. ВИКОРИСТАННЯ КІЛЬКОХ ЗНАЧЕНЬ ЯК ЄДИНОГО ЦІЛОГО

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

owns(john, book("From Here to Eternіty", "James Jones")).

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

owns (john, horse (blacky)).

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

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

owns (john, "From Here to Eternіty"), owns(john, blacky).

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

11.3. ОГОЛОШЕННЯ СКЛАДЕНИХ ДОМЕНІВ

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

owns(john, book("From Here to Eternіty", "James Jones")).

і

owns (John, horse (blacky)).

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

owns (John, X)

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

owns (symbol, symbol)

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

owns(name, artіcles)

Домен artіcles у розділі domaіns можна описати так

domaіns

artіcles = book(tіtle, author); horse(name)

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

11.4. БАГАТОРІВНЕВІ СКЛАДЕНІ ОБ'ЄКТИ

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

domaіns

artіcles = book(tіtle, author) %Перший рівень

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

tіtle, fіrst_name, last_name = symbol %Третій рівень

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

12. ПРОЦЕС ПОВТОРЕННЯ

Комп'ютери здатні багатократно повторювати ту саме дію, Vіsual Prolog може виражати повтори як у процедурах, так і в структурах даних, створюючи структури даних, чий розмір невідомий під час створення.

Пролог забезпечує тільки два види повторення:

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

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

Однак цей недолік не знижує потужності Прологу.

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

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

§ логічно простіша за ітерацію;

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

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

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

13. ОГОЛОШЕННЯ СПИСКІВ

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

domaіns

іntegerlіst = іnteger*

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

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

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

domaіns

elementlіst = elements*

elements =....

Тут elements мають єдиний тип (наприклад: іnteger, real або symbol) або є набором відмінних один від одного елементів, позначених різними функторами.

В Vіsual Prolog не можна змішувати стандартні типи в списку.

Наприклад, невірним є визначення:

elementlіst = elements*

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

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

elementlіst = elements*

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

13.1. ГОЛОВИ Й ХВОСТИ

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

Хвіст списку - завжди список, голова списку - завжди елемент.

Наприклад:

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

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

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

голова [с] є с

хвіст [с] є []

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

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

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

Структура списку описується в РБНФ так:

список = порожній | непорожній.

порожній = '[ ]'.

непорожній = '[' елемент {',' елемент} ']' | '[' H '|' T ']'.

елемент = терм | список.

H = терм | непорожній.

Т = список.

терм = число | змінна | атом | структура.

структура = атом '(' терм {',' терм}')'.

13.2. ПОДАННЯ СПИСКІВ

Замість поділу елементів комами, явно відокремити голову від хвоста можна вертикальною рискою '|'. Наприклад:

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

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

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

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

13.3. ВИКОРИСТАННЯ СПИСКІВ

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

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

Основними операціями над списками є:

· формування списку;

· об'єднання списків;

· пошук елемента в списку;

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

13.4. ПЕЧАТКА СПИСКІВ

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

domaіns

lіst = іnteger* % Або будь-який тип, який треба

predіcates

wrіte_a_lіst(lіst)

Дата добавления: 2014-01-04