« Назад

Мета: Вивчення процесу уніфікації та пошуку з поверненням

Хід роботи

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

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

Приклад 1 - Пошук рішень з умовами

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

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

Лістинг програми

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

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

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

Змінна 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 в обігу був уніфікований зі змінною Title у правилі, то значення, з яким зв'язується Title при підтвердженні правила, повертається і уніфікується зі змінною X. Змінна Title у разі підтвердження правила має значення "DR NO", тому Visual Prolog виведе:

fleming DR NO

Рис. 1 Результат роботи програми з прикладу 1

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

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

Приклад 2 - Пошук з поверненням

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

Знаючи, що bill любить тільки смачну їжу, вивести, яку саме їжу любить bill.

Лістинг програми

Рис. 2. Результат виконання програми з прикладу 2

Правило, представлене відношенням likes, стверджує, що Білл любить смачну їжу. Так як у реченні likes(Y) значення змінної Y="bill", то виконуються пропозиції, наступні після ключового слова then конструкції if ... end if.

Увага:

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

Намагаючись узгодити підціль food(X), Visual Prolog (починаючи з вершини) робить зіставлення з кожним фактом або заголовком правила, що зустрічається у програмі. Він виявляє відповідність із запитом у першого ж факту, представляють відношення food. Таким чином, змінна X зв'язується зі значенням brussels_sprouts. Оскільки існує більш, ніж одна можлива відповідь на звернення food(X), Visual Prolog ставить точку повернення (маркер) біля факту food(brussels_sprouts). Ця точка пошуку з поверненням вказує на те місце, звідки Пролог почне пошук наступної можливої відповідності для food(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), і починається пошук (знову від вершини програми). На цей раз відповідність знайдено, і цільове твердження успішно виконується. В результаті на консоль виводиться слово pizza.

Існує чотири основних правила пошуку з поверненням:

Правило 1: Підцілі повинні бути узгоджені по порядку, зверху вниз.

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

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

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

-- Visual Prolog знаходить відповідну пропозицію, тоді:

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

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

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

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

 

Переривання пошуку з поверненням

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

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

Існує два основні випадки застосування відсікання:

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

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

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

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

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

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

Лістинг програми

Рис. 3. Результат виконання програми з прикладу 3

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

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

1. Пролог звертається до car першої підцілі для предиката buy_car.

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

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

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

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

6. Знаходить відповідність і знову перевіряє колір. На цей раз колір виявляється приємним. Пролог переходить до наступної підцілі в правилі: до перевірки умови Price <25000. Умова виконується.

7. Відбувається виведення на консоль марки автомобіля, його ціни і кольори:

Сorvette red 24000.

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

 

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

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

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

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

Приклад 4 - Запобігання пошуку з поверненням до наступної пропозиції

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

Лістинг програми

Рис. 4. Результат виконання програми з прикладу 4

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

 

Предикат not

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

Приклад 5 - Використання предиката not

Програма демонструє, як можна використовувати предикат not для того, щоб виявити встигаючого студента: студента, у якого середній (GPA) не менше 3,5 і у якого в даний час не продовжується випробувальний термін.

Лістинг програми

Рис. 5. Результат виконання програми з прикладу 5

Увага:

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

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

Ось кілька прикладів коректних і некоректних пропозицій:

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

Якщо змінити пропозицію таким чином, що звернення до not буде виконуватися першим, то вискочить повідомлення про помилку: «Free variables not allowed in not».

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

not (hates (bill, Anyone)), likes (sue, Anyone).

Завдання

Написати довідник і реалізувати для нього наступні предикати:

- Виведення вмісту довідника

- Пошук усіх записів, що задовольняють умові

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

Варіанти завдань:

1. Телефонний довідник

2. Автомобільний довідник

3. Прайс-лист

Контрольні питання

1. Що називається уніфікацією?

2. Що називається пошуком з поверненням?

3. Перерахуйте основні правила пошуку з поверненням.

4.У яких випадках використовується відсікання?

5. Яким чином можна використовувати предикат not?

Зміст звіту:

- титульний аркуш;

- мета роботи;

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

- лістинг програми;

- результат виконання.