Здатність видавати кілька рішень
Відмінною здатністю Пролог є те, що при пошуку рішень на пролозі видається цілий список відповідних значень. Тому, в пролозі один предикат може бути представлений цілим набором правил, кожне з яких може видавати відповідь. Приклад. Нехай є наступний опис предиката "чісло_больше":
Тоді виклик решателя пролог
Видасть відповіді: Більше = 5, 8.
Іншими словами, згідно з правилами в предикате "чісло_больше" більше числа 4 є два числа 5 і 8. Тут видно, що набір правил працює як структура розгалуження case в алгоритмічних мовах. Предикати які можуть видавати кілька значень називаються невизначеними (nondeterm). Предикати, які видають тільки одне значення, називаються певними (determ). Крім невизначених предикатів в пролозі ще використовують механізм невизначеності факти. Приклад.
Тоді виклик решателя пролог
Відповідь буде: Що = квартира, діти
Відкат (Backtracking)
Тепер введемо поняття відкоту (Backtracking). Відкат - це спроба Пролог знайти такий варіант вирішення завдання. Відкат викликається невдачею в деякому місці програми, що приводить прологом до спроби знайти таке рішення. Відкочування йде до місця, де можливо обчислити інше рішення. При цьому всі зв'язані змінні, які були пов'язані нижче точки, де можливий інший варіант рішення, звільняються. При виклику решателя пролог, відкат створюється самим Пролог для видачі всіх значень рішення. Приклад.
Відсікання (Cut)
Тепер введемо поняття відсікання. Відсіканням в пролозі називається механізм, який забороняє перебір правил даного предиката знаходяться нижче поточного правила і забороняє механізм відкату. Відсікання позначається знаком "!". Приклад. Якщо переписати попередній предикат "чісло_болше" як:
Тоді виклик решателя пролог
Видасть відповідь: Більше = 5.
Це відбувається тому, що в кожному правилі предиката, після перевірки на більше, йде оператор відсікання "!", Що забороняє Пролог наступний відкат і пошук інших варіантів відповіді.
Приклад використання механізму відкоту і відсікань.
Механізм відкату і відсікань можна розглянути на наступному прикладі. Припустимо у нас є список значень, в якому потрібно знайти якесь значення і видати стоїть перед ним значення. Так як пролог це логічна мова, то поставлена задача вирішується за допомогою створення набору правил:
При переборі списку, якщо поточний елемент не є шуканим значенням, то робимо перебір далі.
При переборі списку, якщо поточний елемент є шуканим значенням, то припинимо перебір і повернемося на попередній елемент.
Якщо попередні правила не спрацювали, то видати поточний елемент як попереднє значення.
Опис на мові Пролог предиката виконує ці правила буде таке:
Знаючи, що в пролозі можна використовувати порядок розташування правил як спосіб вибору послідовності обходу правил, і знаючи дію механізму відсікань, можна переставити правила 1 і 2 місцями і прибрати перевірку на розбіжність. Тоді отримаємо наступне опис предиката:
Отримане опис складається з трьох правил і виконує наступні дії. Перше правило порівнює поточний елемент з шуканим значенням, і якщо вони рівні, то відбувається а) відсікання правил предиката розташованих нижче від участі в пошуку, б) викликається невдача, що призводить до останову рекурсії. Друге правило робить перебір всіх елементів списку за допомогою виклику самої себе, тобто викликає рекурсию. При цьому, в правилі до виклику рекурсії немає відсікань, і якщо виклик рекурсії буде неуспішним, то управління перейде на правило предиката, розташоване нижче. Якщо виклик рекурсії буде успішний, то викликається відсікання ( "!"), А потім вихід з предиката. Третє правило видає поточний елемент як попереднє значення, яке стоїть перед шуканим значенням, викликає відсікання і вихід з предиката. Дія предиката розглянемо на прикладі. Дамо вирішувачі Пролог рядок:
Пролог робить перший виклик предиката:
- Правило 1 не спрацьовує: 3 не дорівнює 1. Перехід на друге правило:
- Правило 2 викликає рекурсию найті_пред_значеніе (3, [2,4,3,5,2], Попереднє):
- Правило 1 не спрацьовує: 3 не дорівнює 2. Перехід на друге правило:
- Правило 2 викликає рекурсию найті_пред_значеніе (3, [4,3,5,2], Попереднє):
- Правило 1 не спрацює: 3 не дорівнює 4. Перехід на друге правило:
- Правило 2 викликає рекурсию: найті_пред_значеніе (3, [3,5,2], Попереднє):
- Перше правило спрацює: 3 = 3. і виконується: відсікання правил предиката нижче і невдача. Що призводить до виходу з рекурсії з результатом невдачі.
- Продовження правила 2. Невдача виклику рекурсії зі списком [3,5,2] призводить до невдачі другого правила на даному рівні. Пролог переходить на третє правило.
- Правило 3. Тут список = [4,3,5,2]. Відбуваються дії: Попереднє уніфікується з 4, вихід з відсіканням інших можливих рішень.
- Продовження правила 2. Рекурсія повертає вдале значення Попереднє = 4. Відбувається вихід з відсіканням інших можливих рішень.
- Продовження правила 2. Рекурсія повертає вдале значення Попереднє = 4. Відбувається вихід з відсіканням інших можливих рішень.
- Продовження правила 2. Рекурсія повертає вдале значення Попереднє = 4. Відбувається вихід з відсіканням інших можливих рішень.
Відповідь Пролог Попереднє = 4.
Тепер подивимося що буде, якщо прибрати відсікання в другому правилі:
Те Пролог вже видасть кілька результатів:
Це стає можливим, так як включається механізм відкату пролог і в другому правилі з'являється можливість видати відповідь на кожному кроці рекурсії.