Зіставлення та повернення

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

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

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

При намаганні узгодження цілі Пролог вибирає перше з тверджень, голова яких зіставлювана з цільовим; далі необхідно виконати умову правої частини, тобто довести (зліва направо) істинність кон’юнкції підзадач. За умови неуспіху всі змінні, зв’язані в процесі розв’язку попередньої підзадачі, стають вільними і здійснюється перехід до наступного твердження, доки ціль не буде доведена чи не виявиться неможливість доведення. З формальної точки зору, механізм повернення на будь-якій стадії обчислень обробляє поточну ціль – резольвенту. Редукція цілі G полягає у заміні G тілом прикладу, чий заголовок збігається з даною ціллю. Замінена за умови редукції ціль вважається знятою, але з’являються нові цілі – похідні. Дерево виведення складається з вершин та ребер і містить цілі, такі, що „знімаються” у процесі обчислень. Число вершин у ньому дорівнює числу кроків редукції і може служити для порівняння якості різних програм розв’язку однієї задачі. Усі цілі зберігаються у стеку. Для редукції вибирається верхня ціль, вироблювані цілі поміщуються до стеку резольвенти. Для даного запиту може бути кілька успішних обчислень, які дають різні результати.

Роботу механізму повернення та управління ним розглянемо на прикладі. Наведена далі програма у розділі clauses містить факти (у даному випадку інформацію) про результати перескладання екзаменів студентами відповідних груп (номер групи gr – перший компонент структури grex) за відповідними дисциплінами (прізвище, дисципліна, оцінка – компоненти структури examen, яка входить до складу dr). Складна ієрархічна організація інформації може бути застосована для гнучкості формування обговорюваних далі запитів.

Якщо після компіляції програми за зовнішню ціль можна ввести запит типу record (X), у діалоговому вікні буде виведено всі перераховані факти та повідомлення 7 solution

domains

ex = examen (fam, pr, oc) /*(прізвище, предмет, оцінка)*/

fam, pr = symbol

dr, oc = integer

d = drex (dr, ex) /*(номер_ групи, рез-т_ студента)*/

predicates

inscr (g)

clauses

record (grex (261, examen („ІВАНОВ П.Р.”, „Програмування”, 5))).

record (grex (261, examen („ПЕТРОВ Б.О.”, „Операційні системи”,5))).

record (grex (261, examen („СИДОРОВ Т.К.”,”Системи управління”,4)))

record (grex (262, examen („ЖИГОРА С.І.”, „Програмування”,3))).

record (grex (262, examen („ДОНІЙ С.П.”, „Системи управління”,5))).

record (grex (261, examen („ІВАНОВ П.Р.”, „Іноземна мова”,4))).

record (grex (263, examen („СИДОРОВ Т.К.”,„Операційні системи”,5)))

Накладемо обмеження, наприклад, на номер учбової групи. Для зовнішнього запиту record (drex (261, X)) результатом буде

X = examen („ІВАНОВ П.Р.”, „Програмування”,5)

X = examen („ПЕТРОВ Б.О.”, „Операційні системи”,5)

X = examen („СИДОРОВ Т.К.”, „Системи управління”,4)

X = examen („ІВАНОВ П.Р.”, „Іноземна мова”,4)

4 Solution

За запитом record (grex (Z, examen(„ІВАНОВ П.Р.”, X,Y))) отримаємо

Z = 261, X=Програмування, Y=5

Z = 261, X=Іноземна мова, Y=4

2 Solution

Якщо зробити внутрішній запит типу

goal

record (X), write (X).

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

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

show: - record (X), write (X), fail.

Задамо внутрішню ціль

goal

show.

Тут після надходження першого розв’язку змінна Х буде означена константою першого факту: отримане значення змінної Х зіставляється аргументу предиката write(X,) який виведе його на екран. Виконання предикату fail завершиться неуспіхом. Пролог виконує відкат до найближчого недетермінованого (такого, що має декілька варіантів правил) предиката – у нашому випадку record(X). Буде вибрано другий факт, виконано зіставлення і т.д. – дот, поки не закінчиться перебір усіх альтернатив.

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

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