11.4 Відсікання у мові логічного програмування

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

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

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

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

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

11.5 Проблеми появи нескінченних циклів

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

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

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

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

11.6 Рішення проблеми із нескінченними циклами

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

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

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

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

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

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

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

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

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

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