Лекции пролог

quicksort ([ ],[ ]).

, где [X|Xs] – список, который нужно отсортировать,

Ys – отсортированный список,

Хs – то, что нужно разбить на части,

Х – аргумент, относительно которого происходит разбиение

Littles – элементы списка, меньшие Х,

Bigs – элементы списка, большие Х,

partition ([X|Xs], Y, [X|Ls], Bs):– X=Y, partition(Xs,Y,Ls,Bs).

partition([X|Xs],Y, Ls, [X|Bs]):–X>Y, partition(Xs,Y,Ls,Bs).

partition([ ], X,[ ], [ ]).

Упражнение. Построить деревья поиска решений различными алгоритмами сортировки для цели quicksort([1,2,3], List).

Бинарные деревья.

Бинарное дерево содержит два ребра.

Tree (El,Tree1,Tree2).

El – элемент в вершине дерева,

Tree1 – левое поддерево

Tree2 – правое поддерево

binary_tree(nil). – нулевое дерево.

binary_tree(tree(X,L,R)):– binary_tree (L), binary_tree (R).

Программа проверки принадлежности элемента дереву.

tree_member(X,tree(X,L,R)). – x принадлежит дереву, если х – корень дерева.

tree_member(X,tree(Y,L,R)):– tree_member(X,L).

tree_member(X,tree(Y,L,R)):– tree_member(X,R).

Подстановка терма в дерево.

Заменить все вхождения элемента X на Y в заданном дереве.

substitute(X, Y, nil, nil).

substitute(X, Y, tree(X, L, R), tree(Y,L1,R1)):–substitute(X, Y, L, L1), substitute(X, Y, R, R1).

substitute(X, Y, tree(Z, L, R), tree(Z, L1, R1)):–substitute(X, Y, L, L1), substitute(X,Y,R,R1).

Упражнение. Написать аналогичную программу для списков.

Генерирование списка из вершин дерева.

Список можно сформировать по-разному:

1. сверху вниз – [a,b,c] – El, Left, Right.

pre_order(tree(X,L,R),Xs):– pre_order(L,Ls), pre_order(R,Rs), append([X|Ls],Rs,Xs).

pre_order(nil,[ ]).

2. слева направо – [b,a,c] – Left, El, Right.

3. Снизу вверх – [b,c,a] – Left, Right, El.

Символьная математика.

Domains

EXP=const(real);  var(symbol);  mult(EXP, EXP); plus(EXP, EXP);  minus(EXP, EXP);

div(EXP, EXP);  potens(EXP, EXP).

Predicates

d(EXP, EXP, EXP);

Clauses

d(const(_), X, const(Ø)).

d(var(X), var(X), const(1)).

d(var(X), var(Y), const(Ø)):– X<>Y.

d(plus(E1, E2), var(X), plus(E3, E4)):– d(E1, var(X), E3), d(E2, var(X), E4).

d(mult(E1, E2), var(X), plus(mult(E1,E3), mult(E2,E4))):– d(E1, var(X), E4), d(E2, var(X), E3).

Управление порядком вычислений на Прологе.

Отличия логического программирования от Пролога.

1. Правила в Прологе просматриваются сверху вниз, а в логическом программировании правила выбираются произвольно (параллельно).

2. Цели в теле правила (в резольвенте) также обрабатываются слева направо, в логическом программировании цели также выбираются произвольно.

Механизм отката (backtracking).

Рассмотрим следующую программу:

a:– b(X), c(X,Y), d(Y).

b(1).

b(2).

c(1, 2).

c(2, 1).

d(1).

Дерево вывода для нее будет иметь следующий вид:

Откат – это возврат от точки неуспеха назад, к первой недетерминированной подцели для того, чтобы доказать ее заново. В процессе отката теряются все значения переменных, полученные между точкой возврата и неуспеха.

Механизм возврата может быть использован при программировании циклов.

dialog:– [тело цикла], dialog. – так циклы реализовывать нельзя, так как рано или поздно произойдет переполнение стека.

repeat.

repeat:– repeat.

dialog:– repeat, [тело цикла], fail.

Откат

В теле правила все предикаты должны быть детерминированы.

Также можно использовать базу данных, чтобы не терялись значения переменных, необходимых для цикла.

Предикат для реализации цикла со счетчиком.

dialog:– for(I, 1, N), [тело цикла], I>=N.

for(A, A, _).

for(I,A,B):– A<B, A1=A+1, for(I,A1,B1).

Упражнение. Построить дерево поиска решений для следующего правила:

dialog:– N=3, for(I, 1, N), write(I), I>=N.