Сошников Дмитрий Валерьевич к.ф.-м.н., доцент Факультет Прикладной математики и физики Кафедра Вычислительной математики и программирования Московский авиационный институт (государственный технический университет)

©2009 Сошников Д.В. 2 Дерево (в т.ч. дерево выражений) является «родным» типом данных для логических языков Эффективно описываются алгоритмы преобразования деревьев На логических языках, в частности, удобно строить программы преобразования и обработки выражений в символьном виде Дифференцирование Упрощение выражений...

©2009 Сошников Д.В. 3 ?- subst(a,x+10,(a-1)*(a+1),R). R = (x+10-1)*(x+10+1) subst(X,E,X,E) :- !. subst(_,_,X,X) :- atomic(X). subst(X,E,Expr,Res) :- Expr =.. [Op,A,B], subst(X,E,A,A1), subst(X,E,B,B1), Res =.. [Op,A1,B1]. * - a1 + a1 ?- X =.. [f,a,b]. X = f(a,b) ?- f(a,b) =.. X. X = [f,a,b] ?- subst(a,x-10,a*a,R)....

©2009 Сошников Д.В. 4 d(E,X,D) - D есть производная выражения E по переменной X ?- d((x-1)/(x+1),x,R). R = ((1-0)*(x+1)-(1+0)*(x-1))/((x+1)*(x+1)) d(X,X,1) :- !. d(T,X,0) :- atomic(T). d(U+V,X,DU+DV) :- d(U,X,DU), d(V,X,DV). d(U-V,X,DU-DV)) :- d(U,X,DU), d(V,X,DV). d(-T,X,-R) :- d(T,X,R). d(C*U,X,C*W) :- atomic(C), C\\=X, !, d(U,X,W). d(U*V,X,Vd*U+Ud*V) :- d(U,X,Ud), d(V,X,Vd). d(U/V,X,(Ud*V-Vd*U)/(V*V)) :- d(U,X,Ud), d(V,X,Vd).

©2009 Сошников Д.В. 5 rule(A*B,B*A). rule(A+B,B+A). rule(A+B+C,A+(B+C)). rule(A*B*C,A*(B*C)). rule(A*B/C,A*(B/C)). rule(A*(B+C),A*B+A*C). rule(A*(B-C),A*B-A*C). rule(A*B+A*C,A*(B+C)). rule(A*B-A*C,A*(B-C)). rule((A+B)*(A-B),A*A-B*B). rule(A*A-B*B,(A+B)*(A-B)). rule(A*X+X,(A+1)*X). rule(X,X). compute(X+Y,Z) :- integer(X), integer(Y), Z is X+Y. compute(X*Y,Z) :- integer(X), integer(Y), Z is X*Y. compute(X-Y,Z) :- integer(X), integer(Y), Z is X-Y. compute(1*X,X). compute(0*X,0). compute(0+X,0). compute(X/X,1). expr(Expr,Res) :- Expr =.. [Op,A,B], expr(A,A1), expr(B,B1), R =.. [Op,A1,B1], (compute(R,Res);rule(R,Res)). expr(X,X) :- atomic(X).

©2009 Сошников Д.В. 6 Упрощение работает только для двух последовательных веток дерева Выражения типа 1+x+1 не упрощаются! ?- expr(1+1+x,R). R = x+2 ? ; R = 2+x ? ; R = x+(1+1) ? ; R = 1+(1+x) ? ; R = 1+1+x ? ; R = x+(1+1) ? ; R = 1+(1+x) ? ; R = 1+1+x ? ; ?- expr(1+x+1,R). R = 1+(x+1) ? ; R = x+(1+1) ? ; R = x+1+1 ? ; R = 1+(1+x) ? ; R = 1+(x+1) ? ; R = 1+x+1 ? ;

©2009 Сошников Д.В. 7 «Наивный» вариант: convert(E,R) :- expr(E,R). convert(E,R) :- expr(E,E1), convert(E1,R). Проблема: зацикливание Аналогично наивному поиску в лабиринте convert(X,R) :- search([X],[R|_]). search(R,R). search(P,R) :- prolong(P,P1), search(P1,R,D1). prolong([X|T],[Y,X|T]) :- move(X,Y), not(member(Y,[X|T])). Проблема: сложность установления неравенстве выражений

©2009 Сошников Д.В. 8 Для упрощения следует проводить поиск в направлении уменьшения сложности cost(X,0) :- number(X). cost(X,1) :- atom(X). cost(X,Z) :- X =.. [Op,A,B], cost(A,CA), cost(B,CB), Z is CA+CB+2. Реализуем поиск методом градиентного спуска На каждом шаге двигаемся в направлении максимального упрощения выражения Основной предикат: search/4, с аргументами: текущий список выражений для рассмотрения, все выражения предполагаются одинаковой стоимости C; стоимость C выражений в списке; результирующее упрощенное выражение; список выражений длины C, которые уже были рассмотрены.

©2009 Сошников Д.В. 9 Отфильтровываем выражения с весом, меньшим C simplify(E,R) :- cost(E,C), search([E],C,R,[]). move_grad(E1,E2) :- expr(E1,E2), bettereq(E2,E1). bettereq(E1,E2) :- cost(E1,C1), cost(E2,C2), C1=

©2009 Сошников Д.В. 10 В процессе поиска возможны три варианта: Мы получили выражения меньшей длины, отбрасываем исходный и рассматриваем новый список search([X|T],C,R,Ban) :- setof(Z,move_grad(X,Z),L), C1 is C-1, filter(L,C1,L1), L1\=[], search(L1,C1,R,[]). Мы получили выражения такой же длины search([X|T],C,R,Ban) :- setof(Z,move_grad(X,Z),L), C1 is C-1, filter(L,C1,L1), L1=[], appenduniq(T,L,Q), removeall(Q,[X|Ban],Res), search(Res,C,R,[X|Ban]). Ни одно новое выражение не получается – все выражения текущей длины С не могут быть укорочены search([X],_,X,_).

©2009 Сошников Д.В. 11 Определение.Пусть E 1 и E 2 два выражения с множеством переменных. Эти выражения называются P-равными (E 1 = P E 2 ) на множестве P R n, если x P E 1 | x = E 2 | x Для сравнения выражений определим предикат peq Задавать множества значений будем Диапазон: x:(-10,10) Перечисление: y:[1,2,3] ?- peq([x:[1,3,7,11],y:(-10,10)],x*(y-1)+y*(x-1),2*x*y-x-y). yes

©2009 Сошников Д.В. 12 peq(L,E1,E2) :- not(pneq(L,E1,E2)). pneq([],E1,E2) :- C1 is E1, C2 is E2, C1\=C2. pneq([Var:(L,R)|T],E1,E2) :- for(I,L,R), subst(Var,I,E1,R1), subst(Var,I,E2,R2), pneq(T,R1,R2). pneq([Var:L|T],E1,E2) :- member(I,L), subst(Var,I,E1,R1), subst(Var,I,E2,R2), pneq(T,R1,R2).

©2009 Сошников Д.В. 13 ?- X vis [1,2]+2*[3,4]. X = [7,10] ?- X vis [1,2]*[3,4]+2. X = 13 ?- X vis [1,2]*[2,3]*[4,5]. X = [32,40] ?- X vis [1,2]*[2,3]*[4,5]*[3,4]. X = 256

©2009 Сошников Д.В. 14 vmult([],_,[]). vmult([X|T],Y,[X1|T1]) :- X1 is X*Y, vmult(T,Y,T1). vadd([],[],[]). vadd([X|T],[Y|R],[U|S]) :- U is X+Y, vadd(T,R,S). smult([X],[Y],Z) :- Z is X*Y. smult([X|T],[Y|R],Z) :- smult(T,R,Z1), Z is Z1+X*Y. comp(*,A,B,R) :- vector(A), integer(B), vmult(A,B,R). comp(*,A,B,R) :- vector(B), integer(A), vmult(B,A,R). comp(*,A,B,R) :- vector(A), vector(B), smult(A,B,R). comp(*,A,B,R) :- integer(A), integer(B), R is A*B. comp(+,A,B,R) :- vector(A), vector(B), vadd(A,B,R). comp(+,A,B,R) :- integer(A), integer(B), R is A+B. vector([ ]). vector([_|_]). :- op(700,xfx,vis). R vis Expr :- Expr =.. [Op,A,B], A1 vis A, B1 vis B, comp(Op,A1,B1,R). X vis X :- vector(X); integer(X).

©2009 Сошников Д.В. 15 За счёт естественного представления деревьев, языки логического программирования оказываются удобными для задач обработки древовидных структур, в т.ч. преобразования выражений Для полного символьного преобразования выражений можно определить операцию одношагового эквивалентного преобразования (перестройки одного уровня дерева) Эквивалентные преобразования выражений строятся как транзитивные замыкания одношагового отношения при помощи известных алгоритмов поиска