s_program(Ans,Res)

тоді вона побудує відповідь:

Ans = ["b", "=",...]

Res = program([assign("b", int(2)), if_then_else(var("b"),

assign("a",int(1))........])

8.1.Визначте два предикати парнадовжина (Список) і непарнадовжина (Список), таким чином, щоб вони були істинними, якщо їх аргументом є список парної або непарної довжини відповідно.

8.2.Визначте предикат паліндром (Список). Список називається паліндромом, якщо він читається однаково, як зправа наліво, так і зліва направо. Наприклад [м,а,д,а,м].

8.3.Визначте відношення переклад(Список1, Список2) для модифікації списка чисел від 0 до 9 в список відповідних слів.

Наприклад,

переклад ([3,1,7],[три,один,сім])

8.4.Визначте відношення лінеризація (Список1, ЛінійнийСписок), де ЛінійнийСписок - це той же список, але “вирівняний” таким чином, що елементи його підсписків складають один лінійний список.

Наприклад:

goal: лінеризація ([a,d,[c,d],[],[[[e]]],f],L).

L=[a,b,c,d,e,f].

9. ТЕХНІКА ПРОГРАМУВАННЯ В ПРОЛОЗІ.

В цьому розділі ми розглянемо базові підходи до реалізації основних типів алгоритмів в Пролозі.

9.1.Принципи побудови експертної системи.

Розглянемо наступну задачу. Потрібно реалізувати експертну систему, яка б визначала тварину, яку мав на увазі користувач із семи зазначених. Експертна система знайде тварину за допомогою опитування користувача. Цей приклад демонструє бектрекінг для перегляду бази даних і показує ефективне використання предикату not. Типовим діалогом користувача з експертною системою може бути наступний:

goal: run.

Has it hair?

yes

does it eat meat?

yes

has it a fawn color?

yes

has it dark spots?

yes

Your animal may be a (an) cheetah!

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

database

xpositive(symbol, symbol)

xnegative(symbol, symbol)

predicates

animal_is(symbol)

it_is(symbol)

ask(symbol, symbol, symbol)

remember(symbol, symbol, symbol)

positive(symbol, symbol)

negative(symbol, symbol)

clear_facts

run

clauses

animal_is(cheetah) :- it_is(mammal),

it_is(carnivore),

positive(has, tawny_color),

positive(has, dark_spots).

animal_is(tiger) :- it_is(mammal),

it_is(carnivore),

positive(has, tawny_color),

positive(has, black_stripes).

animal_is(giraffe) :- it_is(ungulate),

positive(has, long_neck),

positive(has, long_legs),

positive(has, dark_spots).

animal_is(zebra) :- it_is(ungulate),

positive(has,black_stripes).

animal_is(ostrich) :- it_is(bird),

negative(does, fly),

positive(has, long_neck),

positive(has, long_legs),

positive(has, black_and_white_color).

animal_is(penguin) :- it_is(bird),

negative(does, fly),

positive(does, swim),

positive(has, black_and_white_color).

animal_is(albatross) :-

it_is(bird), positive(does, fly_well).

it_is(mammal) :- positive(has, hair).

it_is(mammal) :- positive(does, give_milk).

it_is(bird) :- positive(has, feathers).

it_is(bird) :- positive(does, fly),

positive(does,lay_eggs).

it_is(carnivore) :- positive(does, eat_meat).

it_is(carnivore) :- positive(has, pointed_teeth),

positive(has, claws),

positive(has, forward_eyes).

it_is(ungulate) :- it_is(mammal),

positive(has, hooves).

it_is(ungulate) :- it_is(mammal),

positive(does, chew_cud).

positive(X, Y) :- xpositive(X, Y), !.

positive(X, Y) :- not(xnegative(X, Y)),

ask(X, Y, yes).

negative(X, Y) :- xnegative(X, Y), !.

negative(X, Y) :- not(xpositive(X, Y)),

ask(X, Y, no).

ask(X, Y, yes) :- !,

write(X, " it ", Y, '\n'),

readln(Reply),

frontchar(Reply, 'y', _),

remember(X, Y, yes).

ask(X, Y, no) :- !,

write(X, " it ", Y, '\n'),

readln(Reply),

frontchar(Reply, 'n', _),

remember(X, Y, no).

remember(X, Y, yes) :- assertz(xpositive(X,Y)).

remember(X, Y, no) :- assertz(xnegative(X,Y)).

clear_facts :-

write("\n\nPlease press the space bar to exit\n"),

retractall(_, dbasedom), readchar(_).

run :-

animal_is(X), !,

write("\nYour animal may be a (an) ",X),

nl, nl, clear_facts.

run :-

write("\nUnable to determine what"),

write("your animal is.\n\n"), clear_facts.

Кожна тварина описується деяким числом характерних атрибутів, які вона має або ж не має. Вони задаються в предикатах animal_is і it_is. Питання, на які користувачу потрібно відповісти, реалізуються за допомогою використання предикатів рositive (X,Y) і negative (X,Y). Але система, між іншим, може задати і питання типу :

Does it have hair?

Отримавши відповідь, система приєднує її до попередньої інформації для подальшого використання.

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

database

xpositive(symbol,symbol)

xnegative(symbol,symbol)

Наприклад, твердження , що тварина не має волосся тоді може бути задане таким чином:

xnegative(has,hair).

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

positive(X,Y):-

xpositive(X,Y),!.

positive(X,Y):- not (xnegative(X,Y)), ask(X,Y,yes).

negative(X,Y):-

xnegative(X,Y),!.

negative(X,Y):- not (xpositive(X,Y)), ask(X,Y,no).

Відмітимо, що останні правила, які використовуються тут при визначенні предикатів positive і negative забезпечують реалізацію тієї ситуації, щоб спростування не трапилось раніше, ніж пройшло опитування користувача.

Предикат ask задає питання і організовує обробку відповіді. Якщо відповідь починається з букви Y, тоді система приймає відповідь Yes, а, якщо відповідь починається з N, тоді в якості відповіді приймається - No.

ask(X,Y,yes):- !, write(X,"it",Y,'\n'),

readln(Reply),

frontchar(Reply, 'y',_),

remember(X,Y,yes).

ask(X,Y,no):- !, write(X,"it",Y,'\n'),

readln(Reply),

frontchar(Reply, 'n',_),

remember(X,Y,no).

remember(X,Y,yes):- assertr(xpositive(X,Y)).

remember(X,Y,no) :- assertr(xnegative(X,Y)).

При роботі з базами даних потрібно також пам`ятати наступне. Під час поповнення бази новими фактами, старі факти повинні зсуватись, щоб не затертись новими. Цю функцію в програмі виконує вмонтований предикат retractall, який використовується при визначенні предикату clearfacts.

clear_facts:-

write("\n\n Please press the space bar to exit\n"),

retractall(_, dbasedom),

readchar(_).

Якщо ви попередньо наберете програму і наповните базу, тоді для запуску програми ви можете використати предикат run.

run:-

animal_is(X),!,

write("\nYour animal may be a(an)", X),

nl,nl, clear_facts.

run:- write("\nUnable to determine what"),

write("your animal is.\n\n"),

clear_facts.

9.2. Макетування: задача маршрутизації.

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

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

Нас будуть цікавити питання типу:

* Чи існує пряма дорога з одного міста в інше?

* Які з міст знаходяться на віддалі меншій 10 км від конкретного міста?

Нехай ми будемо реалізовувати карту прототипу, зображену на мал.9.2.

KansasCity

O---------------

Gordon

O--------- O Houston --------O Tampa

Мал.9.2. Карта прототипу.

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

domains

town = symbol

distance = integer

predicates

road(town, town, distance)

route(town, town, distance)

clauses

road(tampa, houston, 200).