Структура програми, домени, предикати та твердження

Пролог-програма містить такі розділи:

· domains – імена та структури об’єктів, використаних у задачі;

· predicates – назви відношень між об’єктами;

· clauses – факти та правила, що описують ці відношення;

· goal – опис цілі розв’язку.

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

У розділі constants об’являються і одночасно задаються використовувані у програмі константи. Інші розділи розглянемо докладніше.

Типи даних у мові Пролог називають доменами. Домен характеризує множину значень, яких може набувати змінна предиката в ході виконання програми. У розділі domains об’являються також нестандартні типи даних для змінних, що застосовуються як аргументи предикатів. Зв’язування домена з конкретним аргументом (місцем) предиката здійснюється у секції predicates. Самі змінні об’яви не потребують.

Документи поділяються на прості та структуровані, стандартні та нестандартні. До стандартних відносяться:

Symbol – символьна константа (ім’я), яка має дві форми запису:

1) послідовність букв, цифр та знаків підкреслювання, яка починається з малої букви;

2) послідовність символів взято в подвійні лапки (приклади: “apple”, “person”, “Студент Ken B.C.”);

String – окремий символ між двома апострофами;

Integer – ціле число (у діапазоні від –32768 до +32767);

Real – дійсне число у звичайній чи експоненціальній формі запису, причому значення має бути у стандартному для ПЕОМ діапазоні ступенів 10:від -307 до +308. Приклади: -34.567, 0.654, 9.76е+3.

Змінна з іменем “-” (анонімна) використовується, -, -, -, -) мова йде про всі книги написані певним “змінним” Автором, причому опущеними є назва, видавництво, місце та рік видання ролі не відіграють.

Об’яви нових доменів з використанням стандартних має вигляд:

< ім’я > = < ім’я _ стандартного _ домену >

Приклади об’яв:

domains

a = integer

fax = symbol

r, dup = real

Об’яви типу r=real пришвидшують набирання програми. Введення „авторських” найменувань доменів дає змогу внести до програми більше семантики та полегшує контроль типів значень змінних, оскільки змішувати в ході виконання програми змінні формально різних типів (доменів) не можна.

Приклад:

domains

person, thing = symbol

predicate

likes (person, thing)

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

Для одного предиката припускається кілька оголошень, наприклад, можна оголосити, що предикат member працює з числами та іменами шляхом задання таких оголошень:

predicates

member (name, namelist)

member (number, numberlist).

У цьому прикладі вважається, що аргументи name, namelist, number, numberlist визначені користувачем. Альтернативні оголошення для number повинні мати однакове число аргументів.

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

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

domains

articles = book (title, author); …

author = author (init, fam)

title, author, fam = symbol

init = string

У запису доменів функторів крапка з комою замінює союз „чи”. Кожна альтернатива має містити єдиний функтом і опис доменів для безпосередніх компонентів. У реченні date (e, may, 2000) термін date – функтор, а інші об’єкти – аргументи. Аргументами також можуть бути функтори. Це природно породжує деревовидні структури. Приклади – опис складного електричного кола, арифметичного виразу, синтаксичної структури речення. Корінь дерева називається головним функтором.

Розділ predicates має містити повний перелік предикатів користувача, застосовуваних у програмі. Опис предикату включає ім’я предиката та список його аргументів:

< ім’я _ предикату > (<d1>, <d2>,..., < dN>)

Тут <d1>, <d2>,..., < dN> – імена стандартних доменів або імена доменів, оголошених у розділі domains. Предикати використовуються для зображення як даних, так і правил їх обробки.

Один і той самий предикат може мати різне число аргументів; такі предикати оголошуються для кожного варіанта окремо. Приклади оголошення предикатів:

predicates

add (integer, integer, integer)

lk (fr)

lk (d1, d2).

У розділі clauses описуються твердження стосовно предикатів. Заперечення предиката pr задається у формі not (pr) і припустиме тільки у хвостовій (правій) частині правила.

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

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

собака (X): = батько (X,Y), собака (Y).

Читається: „Всякий X – собака за умови, що батьком X є Y і об’єкт Y – собака” (звичайною мовою: „Усякий сучий син – собака”). Квантор та зв’язка типу, якщо мають на увазі!!

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

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

У тілі правила, окрім оголошених у програмі предикатів, можуть використовуватися стандартні предикати та операції порівняння. Стандартні предикати виконують різноманітні функції з виконання введення – виведення різних типів даних, у роботі з файлами та ін. Логічним значенням такого предиката є код повернення виконуваної операції („істина” за умови успішного її завершення).

Арифметичні вирази у мові Пролог будуються з використанням предметних змінних, знаків арифметичних операцій та стандартних функцій abs, sin, cos, tg, arctg, exp, ln, log, sgrt та ін. Операції div, mod дають частку та залишок від ділення націло. Звичайне ділення цілих аргументів дає дійсний результат. При зведенні Х у ступінь Z доводиться, як і в мові Паскаль, застосовувати конструкцію exp (Z*ln (X)). Відсутню у системі функцію sign(x) можна замінити відношенням x/abs(x).

У правилах можливо використовувати операції порівняння („не рівно” записується у паскалівському стилі – як <>). Наприклад, перевірку Х на непарність можна записати Х mod 2 <> ().

Основними джерелами введення-виведення даних для програми мовою „Пролог” здійснюється з використанням предикатів write ( ). Числові дані за умовчанням виводяться у форматові з фіксованою крапкою (11 значущих цифр). Форматне виведення з точкою, що пливе, організується конструкцією типу:

writef („ДР=% е” ДР)

за якою виводиться текст до знаку %, а далі 11 розрядна мантиса та двозначний порядок змінної ДР. При заміні у форматній стрічці букви e на f буде виведене 11-значне число з фіксованою крапкою.

Окремо записуваний предикат n1 виконує переведення стрічки.

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

goal

synonim (brave, X),

write (“a synonim for ‘brave’ is”),

n1,

write („ ’ ”),

n1.

Змінні у запитах (цілях) пов’язані квантором існування: з’ясовується, чи є таке значення змінної, коли відповідь на питання буде логічним наслідком програми. „Екзистенціальний” запит у загальному випадку має кілька рішень (відповідей). Окремим випадком запитів є кон’юнктивні – коли є змінна, що входить до декількох цілей запиту.

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

/*Програма „Родичі” */

domains

person = symbol

predicates

male (person)

female (person)

parents (person, person, person) /*(дитина, батько, мати)*/

sister (person, person) /*(сестра, брат)*/

who _ is _the _sister /*без аргументів*/

goal

who_ is_ the_ sister

clauses

/* факти */

male („Федір”)

male („Семен”)

female („Маша”)

female („Дар’я”)

parents („Дар’я”, „Федір”, „Маша”).

/* правила */

who_ is_ the_ sister: -

sister (Sister, Brother),

write (Sister,

„is the sister of”,

Brother), n1.

sister (Sister, Brother): -

female (Sister),

parents (Sister, Father, Mother),

parents (Brother, Fatter, Mother).

Зауважимо, що у відношенні „бути сестрою” спільність батьків забезпечується збігом імен відповідних змінних. Після здійснення підстановки в значенні Sister усіх наявних жіночих імен та перебору можливих варіантів буде знайдено єдино досяжну ціль: Дар’я is the sister of Семен.

Розділ опису цілей може бути відсутній; тоді зовнішній запит вводиться у діалоговому вікні після запуску програми на виконання. Під час використання зовнішньої цілі Пролог відшукає всі варіанти розв’язків; у цьому самому вікні буде виведено значення змінних предикатів та повідомлення про кількість розв’язків. Орієнтація на зовнішні запити дає змогу некваліфікованим користувачам використовувати складену фахівцем програму з різними цілями без її перекомпіляції.