Хлопець(степан)

дівчина(оксана).

дівчина(марія).

дівчина(галина).

У програмі визначено, що X і У утворюють можливу пару, якщо X є хлопцем, а У — дівчиною. Тепер давайте подивимося, які можливі пари є:? — можлива_пара(Х, У).

X = іван, Y = оксана;

X = іван, Y = марія;

X = іван, Y = галина;

X = петро, Y = оксана;

X = петро, Y = марія;

X = петро, Y = галина;

X = василь, Y = оксана;

X = василь, Y = марія;

X = василь, Y = галина;

X = степан, Y = оксана;

X = степан, Y = марія;

X = степан, Y = галина.

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

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

/*1*/ ціле_число(0).

/*2*/ ціле_число(X):—ціле_число(У), Х is У+1.

Якщо ми поставимо питання

?— ціле_число(X).

те отримаємо в якості можливих відповідей усі цілі числа в порядку зростання (0, 1, 2, 3,...), по одному числу кожного разу. Всякий раз, коли ініціюється повернення (можливо, в результаті введення крапки з комою ';'), для предиката ціле_число знаходиться нове зіставлення, внаслідок чого його аргументу привласнюється чергове ціле число.

Спочатку для відповіді на питання є вибір між фактом 1 і правилом 2. Якщо вибирається факт 1, то нічого більшого вибирати не доведеться, і ми отримуємо X=0. Інакше вибирається правило 2 і шукається відповідність для мети, що породжується цим правилом. Якщо вибирається факт 1, то завершується доказ цільового твердження з відповіддю X=1; інакше використовується правило 2 і знову шукається відповідність для підцілі, що з'явилася. І так далі. На кожному етапі перше що робить Пролог — це вибирає факт 1. Тільки при виконанні повернення він змінює останній зроблений ним вибір. Кожного разу, коли він це робить, він повертається до того місця, де востаннє вибирав факт 1, і вибирає замість нього правило 2. При цьому виборі з'являється нова підціль. Факт 1 представляє першу можливість для зіставлення з цією підціллю.

22. Відсікання.

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

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

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

В деяких випадках включення відсікання в програму може означати перехід від програми, яка не працюватиме, до програми, яка працюватиме.

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

Ми можемо виділити три основні випадки використання відсікання.

Перший пов'язаний з ситуаціями, коли ми хочемо вказати Пролог-системі, що вона знайшла потрібне правило для заданого цільового затвердження. В цьому випадку відсікання означає: «якщо ви дійшли до цього місця, то ви вибрали саме те правило, яке потрібне для цього цільового затвердження».

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

До третього випадку відносяться ситуації, коли ми хочемо закінчити породження альтернативних рішень механізмом повернення. В цьому випадку відсікання означає: «якщо ви дійшли до цього місця, то ви знайшли єдине рішення задачі і ніякої можливості знайти інші альтернативні рішення немає».

 

23. Підтвердження правильності вибору правила.

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

сума(1,1):-!.

сума(N, Результат):- N1 is N-1, сума(N1, Результат), Результат is Результат+N.

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

 

24. Комбінація «відсікання-fail».

Предикат fail не має аргументів, це означає, що виконання цільового твердження fail не залежить від того, які значення мають змінні. Дійсно, предикат fail означений таким чином, що доказ його узгодженості як цільового твердження завжди закінчується невдачею і призводить до включення механізму повернення. Якщо fail зустрічається після відсікання, то нормальне виконання повернення зміниться в результаті дії механізму відсікання. Ця комбінація «відсікання-fail».

Давайте означимо предикат середній_платник_податків, де середній_платник_податків(X) означає, що X є середнім платником податків.

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

середній_платник_податків(Х):- іноземець(Х), fail

середній_платник_податків(Х):-...

У цьому витягу з програми (яка є невірною) в першому правилі робиться спроба сказати: «якщо X — іноземець, то доказ узгодженості цільового твердження середній_платник_податків(X) повинен закінчитися невдачею». Друге правило повинне використати загальний критерій того, що означає бути середнім платником податків в тих випадках, коли X — не іноземець. Помилка полягає в тому, що якби ми звернулися з питанням:

?— середній_платник_податків(Гейц).

про іноземця на прізвище Гейц, то сталося б зіставлення з першим правилом і узгодженість цільового твердження іноземець була б доведена. Далі, цільове затвердження fail ініціювало б повернення. При спробі знайти нове зіставлення для мети середній_платник_податків Пролог знайшов би друге правило, що визначає загальні критерії обчислення податку, і почав би застосовувати це правило до Гейц. Цілком імовірно, що цей іноземець задовольняв би загальним критеріям, що привело б до невірної відповіді «так».

Ми можемо зробити це, вставивши відсікання перед fail. Дещо ґрунтовніше означення предиката середній_платник_податків, що включає ці зміни, наведено нижче:

середній_платник_податків(Х):- іноземець(Х),!, fail.

середній_платник_податків(X):- дружина(X, Y), дохід(Y, Дохід), Дохід > 3000,!, fail. середній_платник_податків (Х):- дохід(X, Дохід), 2000 < Дохід, 20000 > Дохід.

дохід(Х, Y):- отримувана_зарплатня(Х, Р), Р < 5000,!, fail.

дохід(Х, Y):- платня(Х, Z), дохід_від_капіталовкладень(Х, W), Y is Z+W. дохід_від_капіталовкладень(Х, Y):-...

Як і в першому випадку застосування відсікання, ми можемо замінити будь-яке використання комбінації «відсікання-fail» використанням предиката not. Така заміна вимагає дещо більшої реорганізації програми, але при цьому не призводить до втрати ефективності.

середній_платник_податків(Х):- not(іноземець(Х)), not((дружина(X, Y), дохід(Y, Дохід), Дохід>3000)), дохід(Х, Дохід1),...

25. Завершення «породження і перевірки».

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

розділити(N1, N2, Результат):- ціле_число(Результат),

Добуток_1 is Результат *N2,

Добуток_2 is (Результат+1)*N2,

Добуток_1 =< N1, Добуток_2>N1,!.

Це правило використовує предикат ціле_число для породження числа Результат, яке є результатом «ділення» N1 на N2. Так, наприклад, результат ділення 27 на 6 рівний 4, оскільки 4x6 менше або рівне 27, а 5x6 більше ніж 27.

Приведене правило використовує предикат ціле_число як «генератор», а інші цільові твердження виконують функцію відповідного «контролера».Якщо задані конкретні значення N1 і N2, то предикат розділити(N1,N2,Результат) може мати значення «істина» лише для одного можливого значення Результат. Незважаючи на те що ціле_число може породити нескінченну безліч кандидатів, лише для одного з них виконуватимуться останні тести. Ми можемо явно виразити це наше знання, вставивши відсікання у кінці правила. Словами це можна сказати так: «якщо нам вдалося породити число Результат таке, що воно успішно проходить тести для числа, що є результатом ділення, то немає потреби намагатися отримати інше рішення». Зокрема, немає необхідності переглядати який-небудь з виборів, які були зроблені при пошуку правил для розділити, ціле_число і так далі. Ми знайшли єдине рішення, і немає підстав шукати інше. Якби ми «не» додали відсікання, то будь-яке повернення врешті-решт знову ініціювало б пошук альтернатив для ціле_число. Так що продовжилося б породження значень для змінної Результат.

 

26. Проблеми, пов'язані з використанням відсікання.

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

Означимо предикат число_батьків, який дає інформацію про те, скільки батьків має людина. Ми можемо означити його таким чином:

число_батьків(адам, 0):-!.

число_батьків(єва, 0):-!.

число_батьків(Х,2).

Що станеться, якщо ми використовуємо ті ж самі правила, щоб перевірити, що ця людина має це число батьків. Усе добре, за винятком того, що ми отримуємо

?— число_батьків(єва,2).

True

Наша реалізація обробки «інших» випадків, заснована на використанні відсікання, просто більше не працює належним чином. Існують два способи змінити означення, які дозволили б нам усунути вказаний ефект:

число_батьків(адам, N):-!, N=0.

число_батьків(єва, N):-!, N=0.

число_батьків(Х, 2).

Звичайно, ці означення як і раніше не працюють, якщо задати цільове затвердження виду

?— число_батьків(Х,Y).

чекаючи, що повернення дозволить перерахувати усі можливості. Таким чином, можна зробити наступний висновок:

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

 

27. Вивід термів.

Найбільш зручний спосіб надрукувати деякий терм на дисплеї терміналу полягає, мабуть, у використанні вбудованого предиката write. Якщо значенням змінної X є терм, то поява цілі write(X) викличе друк цього терма на дисплеї. У випадку якщо змінна X неконкретизована, буде надруковано деяке унікальне ім'я, яке складається з одних цифр (наприклад, '_253'). Проте якщо дві змінні «зчеплені» в межах одного і того ж аргументу предиката write, то їм буде відповідати одна і та ж змінна. Предикат write не можна погоджувати знову. Цей предикат виконується лише один раз.

Вбудований предикат nl застосовується для переходу на новий рядок при друці даних на дисплеї. Назва “nl” утворена від “new line”. (новий рядок). Як і write, предикат nl виконується тільки один раз. Наступний вбудований предикат tab використовується для друку пропусків на екрані дисплея. Цільове затвердження tab(X) виконується тільки раз і викликає переміщення курсора на X позицій вправо. Передбачається, що значення змінної X — ціле число.

Означимо предикат рр (pretty print — «хороший друк») так, що цільове затвердження рр(Х,Y) друкує в зручному вигляді список, присвоєний в якості значення змінної X.

Наприклад, список[ 1,2,3] «добре» друкується в наступному вигляді:

а список [1,2,[3,4],5,6] друкується як

Якщо елемент списку є структурою, то він оброблятиметься таким самим способом, що і атом.

pp([H|T],I):-!, F is I+3, pp(H,F), ppx(T,F),nl.

pp(X,I):- tab(I), write(X),nl.

ppx([],_).

ppx([H|T],I):- pp(H,I), ppx(T,I).

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