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

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

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

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

- Перший аргумент VarName визначає який з аргументів в зазначеному предикаті потрібно відібрати в список;

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

- Третій аргумент, ListParam, з змінною, якою позначається список значень, зібраних через перебір з поверненнями.

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

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

domains

name, address = string

age = integer

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"]

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

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

domains

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

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(string)

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) */

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

write("First List:", Ans), nl,nl,

/*The trick is to write the list first, than add the functors *

* append([apple,[[[47], '\1']], [[["This is a string",b,7, *

* 'w']],bee], ['c'], Ans2) */

*

append([l[s("This"), s("is",s("a"),s("list"))]), s(bee)],

[c('c')], Ans2),

write("Second List :", Ans2), nl.

clauses

/* Concatenate two lists */

append([], L, L).

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

8.6.Реалізація синтаксичного аналізу за допомогою списків.

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

Розіб'ємо задачу на дві підзадачі: сканування і синтаксичний аналіз.

Розглянемо програму:

domains

toklist = string*

predicates

tokl(string, toklist)

clauses

tokl(Str, [H | T]):-fronttoken(Str,H,Str1),!,

tokl(Str1,T).

tokl(_,[]).

/* Друга частина програми є синтаксичним аналізатором */

domains

program = program(statementlist)

statementlist = statement*

/* визначення типу оператора */

statement = if_Then_Else(exp,statement, statement);

if_Then(exp,statement);

while(exp,statement);

assign(id,exp)

/* визначення виразу */

exp = plus(exp,exp);

mines(exp,exp);

var(id);

int(integer)

id = string

predicates

s_program(toklist, program)

s_statement(toklist, toklist, statment)

s_statementlist(toklist, toklist, statmentlist)

s_exp(toklist, toklist, exp)

s_exp1(toklist, toklist, exp, exp)

s_exp2(toklist, toklist, exp)

clauses

s_program(List1, program(Statementlist)):-

s_statementlist(List1, List2, Statementlist),

List2 = [].

s_statementlist([], [],[]):-!.

s_statementlist([List1, List4, [Statement | Program]):-

s_statement(List1, List2, Statement),

List2 = [";" | List3],

s_statementlist(List3, List4, Program).

s_statement(["if" | List1], List7,

if_theh_else(Exp,Statement1, Statement2)):-

s_exp(List1,List2, Exp),

List2 = [ "then" | List3],

s_statement(List3, List4, Statement1),

List4 = ["else" | List5],!,

s_statement(List5, List6, Statement2),

List6 = ["fi" | List7].

s_statement([" if.....

. . .

s_statement([ " do .....

. . .

s_statement([Id | List1], List3, assign(Id,Exp)):-

isname(Id),

List1 = ["=" | List2],

s_exp(List2,List3,Exp).

s_exp(List1,List3,Exp):-

s_exp2(List1,List2,Exp1),

s_exp1(List2,List3,Exp1,Exp).

s_exp1(["+" | List1],List3,Exp1,Exp):-!,

s_exp2(List1,List2,Exp2),

s_exp1(List2,List3,plus(Exp1,Exp2), Exp).

s_exp1(["-" ........

s_exp1(List,List,Exp,Exp).

s_exp2([Int | Rest],Rest, int(I)):-str_int(Int,I),!.

s_exp2([Id | Rest],Rest,var(Id)):-isname(Id).

Предикат tokl є сканером; він аналізує стрічку і перетворює її в список лексем.

Всі предикати, які починаються з s є предикатами синтаксичного анализу. В цьому прикладі вхідний текст є программою на псевдопаскалі. Вона включає оператори: IF THEN ELSE, IF THEN, DO WHILE і ASSIGNMENT. Для побудови виразів використовуються дії додавання і віднімання над змінними і константами цілого типу.

Програма працює наступним чином:

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

2.Предикат s_statement приймає той же список лексем і перевіряє чи зможуть лексеми бути разділені на індивідуальні твердження, кожне з яких закінчується крапкою з комою.

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

а)Чотири фрази s_statement відповідають чотирьом типам операторів псевдопаскалю. Вони аналізуються послідовно.

б)Потім проводиться порівняння з виразами.

4.Предикати sexp, s_exp1 і s_exp2 працюють аналогічно з s_statment, але тільки по відношенню до виразів.

Якщо системі побудувати запит:

goal: tokl("b=2;

if b then a=1 else a=2 fi;

do a=a-1 while a