Шекет В.І. Конспект лекцій по логічному програмуванню

Подождите немного. Документ загружается.

domains

list = integer*

predicates

length_of(list, integer)

clauses

length_of([], 0).

length_of([_|T], L) :- length_of(T,

TailLength),

L = TailLength + 1.

Поглянемо спочатку на другу фразу. Так,

length_of[_,|T] порівнює любий непустий список,

прив`язуючи T до хвосту списка. Значення голови не суттєво,

ЕОМ буде її рахувати як один елемент.

Так ціль

goal:length_of([1,2,3],L) ,

використовуючи другу фразу, зв'яже з T значення [2,3].

Наступний крок - обчислити довжину T. Коли це зроблено, не

важливо як, тоді TailLength отримає значення 2, і ЭВМ потім

зможе добавити до неї 1 та прив'язати L до 3.

Для того, щоб визначити довжину [2,3]

рекурсивно викличеться length_of([2,3],TailLength. Ця

ціль зрівнює другу фразу, прив'язуючи - [3] до T . Тепер

виникає задача, як знайти довжину [3], яка дорівнює 1, а

потім добавить 1, щоб отримати довжину [2,3], яка буде 2. І

так далі і тому подібно. Тому length_of знов викличе себе

рекурсивно, щоб отримати довжину списку [3]. Хвіст для [3]

рівний [ ], тому T зв'яжеться з [], і задача зараз полягає в тому ,

щоб знайти довжину [], потім додати до неї 1, і знайти

довжину [3].На цей раз це зробити легко. Ціль

length_of([],Tail Length зрівнюючи першу фразу,

зв'яже TailLength з 0. Тепер ЭОМ може додати 1 до неї,

отримуючи довжину списку [3] і повернутися до фрази

виклику. Яка , в свою чергу , прибавить знову 1 , отримуючи

довжину [2,3] і повернеться до фрази, яка викликала її; ця

початкова фраза прибавить знову 1 , знаходячи довжину

списку [1,2,3].

Рисунок 8.1 показує дійсний процес обчислення довжини

списку. Ми використали тут різні змінні, щоб підкреслити той

факт, що змінні з одинаковими іменами в різних фразах , або

різних викликах однієї і тієї ж фрази, будуть різними.

length-of([1,2,3],L1)

length-of([2,3],L2)

length-of([3],L3)

length-of([],0)

L3 = 0 + 1 = 1

L2 = L3+ 1 = 2

L1 = L2+ 1 = 3

Рис.8.1-Обчислення довжини списку.

8.2.3 Іще один варіант підрахунку довжини списку

Як ви бачите, предикат length_of не є хвостовою

рекурсією. Чи можливо створити рекурсивно-хвостовий

предикат визначення довжини списку? Можливо, але для

цього потрібно прикласти певні зусилля.

Проблема з length_ of заключається в тому, що ми не

можемо обчислити довжину списку, пока не підрахуємо

довжину хвоста. Та все ж така можливість мається.

Використаємо предикат з трьома аргументами.

- Перший є список, котрий ЕОМ буде читати при

кожному виклику, поки він не стане пустим.

- Другий є вільним аргументом, який в кінці роботи буде

визначати результат.

- Третій є лічильником, котрий починається з 0 і

збільшується з кожним викликом. В кінці лічильник

можна уніфікувати з незв'язаним результатом.

Наступна програма реалізує наш підхід.

domains

nteger* list = i

predicates

h_of(list, integer, integer) lengt

clauses

/ * * * * * * * * * * * * * * * * * * * * * * *

* Якщо список пустий, тоді уніфікувати другий

* ату з третім * результуючий аргумент предик

* аргументом - лічильником *

* * * * * * */ * * * * * * * * * * * * * * * *

length_of([], Result, Result).

/* * * * * * * * * * * * * * * * * * * * * * *

* * * *

* В іншому випадку, додати 1 до лічильника і

р * екурсивно

* зв`язати результат цього кроку з результатом

в майбутньому. *

* * * * * * * * * * * * * * * * * * * * * * *

* * * */

length_of([_|T],Result,Counter):-

NewCounter=Counter + 1,

length_of(T, Result, NewCounter).

Запит до цієї програми повинен також мати вмонтований

предикат друку. Наприклад:

goal:length_of([1,2,3],L,0), /* починає з

значенням Counter = 0 */

write(L),nl.

Остання версія програми length_of більш складна і

менш логічна.

8.2.4 Модифікація списку

Модифікація списку заключається в якійсь зміні уже

існуючого списку. Традиційно, така зміна проводиться

послідовною обробкою елементів списку. Прикладом

модифікації списку може служити програма, яка додає до

кожного елементу списку 1.

Обчислення, які повинна виконувати програма, можна

описати наступним чином:

1.Зв'язати голову і хвіст початкового списку відповідно з

Head і Tail.

2.Зв'язати голову і хвіст результату з Head1 і Tail1

(Head1 і Tail1 ще не мають значень).

3.Додаючи 1 до Head, отримаємо Head1.

4.Рекурсивно додайте 1 до всіх элементів Tail, отримаєте

Tail1.

Наступна програма реалізує запропонований алгоритм.

domains

list = integer*

predicates

add1(list,list)

clauses

add1([], []).

add1([Head|Tail],[Head1|Tail1]):-

Head1= Head+1,

add1(Tail,Tail1).

Розглянемо ще одну програму модифікації списку. Вона

ний список і переписує його без від'ємних чисел. сканує вхід

domains

list = integer*

predicates

discard_negatives(list,list)

clauses

discard_negatives([],[]).

discard_negatives([H|T],ProcessedTail):-

/* якщо Н є від`ємним, тоді пропустити його

H < 0, !,

discard_negatives(T,ProcessedTail).

discard_negatives([H|T],[H|ProcessedTail]):-

discard_negatives(T,ProcessedTail).

Наступний предикат копіює елементи списку, повторюючи

їх два рази.

doubletail([],[]).

dou bletail([H|T],[H|H| doubletail]): -

doubletail(T,doubletail).

8.2.5 Належність елемента списку

Припустимо, ми маємо список імен. Нам потрібно

написати предикат, який би встановлював належність якогось

імені (перший аргумент) вибраному списку імен (другий

аргумент ). Нехай цим предикатом буде предикат:

member(name, namelist)

В наступній програмі перша фраза досліджує голову списку.

Якщо голова списку співпадає з іменем, яке ми шукаємо , тоді

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

в даному випадку хвіст списку нас не цікавить, він

характеризується анонімною змінною. Якщо ж імені немає в

голові, тоді його потрібно рекурсивним чином шукати в хвості

списку. За це і відповідає друга фраза програми.

domains

namelist = name*

name = symbol

predicates

is_a_member_of(name,namelist)

clauses

is_a_member_of(Name,[Name|_]).

is_a_member_of(Name,[_|Tail]):-

is_a_member_of(Name,Tail).

8.3 Використання одного й того ж предикату для

вирішення різних задач

Особливість ПРОЛОГУ заключається в тому, що коли ви

будуєте предикат для вирішення якоїсь конкретної задачі , то

він може використовуватись і для вирішення зовсім інших задач.

Продемонструємо це на наступному прикладі. Побудуємо

пре ьома аргументами: дикат конкатенації двох списків з тр

append(List1,List2,List3)

де List3 є результуючим списком. Використаємо наступний

рекурсивний алгоритм.

Якщо перший список пустий, тоді результуючий список

буде рівний другому списку (append([],List2,List2)).

Інакше, головою третього списку становиться голова першого

списку, а хвостом - залишок першого списку і другий список.

Прийдемо до програми:

domains

integerlist = integer*

predicates

append(integerlist, integerlist,

integerlist)

clauses

append([], List, List).

append([X|L1], List2, [X|L3]) :-

append(L1, List2, L3).

Якщо ми задамо ціль

goal: append([1,2],[3,4]), тоді отримаємо список

[1,2,3,4].

З іншого боку, розглядаючи предикат append з

декларативної точки зору, ми визначили відношення між трьома

списками. Таке відношення буде вірним і у випадку, коли буде

відомий тільки третій список. Наприклад,

goal: append(L1,L2,[1,2,4] дасть результат

L1 = [], L2 = [1,2,[1,2,4]

l1 = [1], l2 = [2,4]

. . .

Також ви можете використати предикат append, щоб

визначити який із списків можна додати до списку [3,4], щоб

отримати список [1,2,3,4]. Наприклад, задавши

goal:append[L1,[3,4],[1,2,3,4] матимемо L1

=[1,2]

Предикат append визначає відношення між множинами на

вході і виході. Тому відношення може використовуватись

різними способами. Задаючи таке відношення, ви можете

запитати:

Який вихід відповідає даному входу? або ж

Який вхід відповідає даному виходу?

Статус аргументів даного предикату при виклику, базується

на зразку потоку даних. Предикат append може обробляти

любий зразок потоку даних.

Але не всі предикати Прологу можуть бути викликані

різними зразками потоку даних. Якщо фраза Прологу може

оброблятись різними зразками потоку даних, тоді її називають

інвертованою фразою. Зазначимо, що використання інвертованих

фраз додає потужності вашим предикатам.

8.4 Знаходження зразу всіх розв`язків

Як ми вже зазначали раніше, для задання ітераційних

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

рекурсія. Рекурсія - більш потужніший засіб. Вона,

використовуючи апарат формальних аргументів, може

передавати інформацію від одного виклику до іншого. Іншими

словами, рекурсія дозволяє відсліджувати часткові результати,

аналізувати лічильники.

Але іноді виникає проблема, яку важко вирішити і за

допомогою рекурсії. Нехай вам потрібно знайти зразу всі

розв`язки задоволення цілі, як частини єдиної складної

структури даних. Пролог вирішує дану проблему за допомогою

предикату findall, який приймає ціль як один із своїх

аргументів, збираючи всі розв'язки цієї цілі в один список.

Предикат findall має три аргументи:

- Перший аргумент VarName визначає який з аргументів

в зазначеному предикаті потрібно відібрати в список;

- Другий, Мypredicate, визначає предикат, з якого будуть

збиратись значення;

- Третій аргумент,ListParam, з змінною, якою

позначається список значень, зібраних через перебір з

поверненнями.

Зазначимо, що попередньо повинна бути визначена

область, до якої повинні належати значення ListParam.

Наступна програма використовує findall, для визначення

середнього віку групи людей.

domains

name,address=string

age=integer

100

list=age*

predicates

person(name,address,age)

sumlist(list,age,integer)

goal

findall(Age,person(_, _, Age),L),

sumlist(L,Sum,N),

Ave = Sum/N,

write("Average =", Ave),nl.

clauses

sumlist([],0,0).

sumlist([H|T],Sum,N):-

sumlist(T,S1,N1),Sum=H+S1,

N=1+N1.

person("Sherlock Holmes","22B Baker

Street",42).

person("Pete Spiers","Apt. 22,21st

Street",36).

person("Mary Darrow","Suite 2,Omega

Home",51).

В цій програмі фраза findall створює список L, який

містить числа, які відповідають віку всіх людей з предикату

person. Якщо ви бажаєте зробити список людей вік яких 42

роки, тоді ви можете написати ціль

findall(Who,person(Who,_,42),List).

8.5 Складні списки

Часто вам потрібно зберігати комбинацію різних типів

елементів всередині одного списку, як наприклад

[2,3,5,12,[food,"goo"], "new"]

101

Складними будемо називати списки, які містять більше

одного типу аргументів. Нам будуть потрібні спеціальні

декларації, щоб обробити списки багатотипних елементів, тому

що Пролог вимагає, щоб всі елементи списку належали одній

області. Для опису різнотипних списків потрібно

використовувати функтори.

Наступний приклад декларації області для списку, який

може мати символ, ціле число, літеру, стрічку або ж список із

них. Декларація списку повинна мати функтор, а потім повинна

бути декларована рекурсивно. Так, попередній список повинен

бути описаний:

domains

llist=l(list);s(symbol);i(integer);c(char);t(st

ring)

list=llist *

І буде задаватись в Пролозі:

[i(2),і(3),i(5),i(12),

[c(food),s(“goo”)],s(“new”)]

Наступний приклад з предикатом append показує як

використовувати такий опис:

domains

llist=l(list);s(symbol);i(integer);c(char);t(st

ring)

list=llist *

predicates

append(list,list,list)

goal

makewindow(1,7,7, "answer",15,0,8,80),

/*Note how you can use the same code but need

functors *

*append([likes,[bill,mary]],[bill,sue],Ans)

102