:-use_module(library(lists)).

%\documentstyle[12pt]{article} 
 
%\begin{document}

%\begin{verbatim}
% SYMBOLIC COMPUTATION: using various representations of data.
% COMPUTING DERIVATIVES of POLYNOMIALS
% For the purpose of this program polynomials are functions constructed 
% from a variable x, integers, function symbols *,^ and +, and parentheses. 
% X^N defined for a non-negative integer N and X<>0 only.
% D!lerivative is only computed once. Multiple calls can lead to 
% an infinite loop

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%derivative(F,DF) iff DF is the derivative of F written in canonical 
%form.
%type F, DF - polinomials.
 
%mode derivative(+,-)
derivative(F,Y) :- 
          der(F,G),
          simplify(G,Y).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
%der(F,DF) iff DF is the derivative of F.
%type F, DF - polinomials. 
%mode derivative(+,-).

der(N,0) :-
    number(N). 
der(x,1).
der(F^1,DF) :- 
      der(F,DF).
der(F^N,N*F^M*DF) :-
    N>1,
    M is N-1,
    der(F,DF).
der(E1*E2,E1*DE2 + E2*DE1) :- 
              der(E1,DE1),
              der(E2,DE2).
der(E1+E2,DE1 + DE2) :- 
              der(E1,DE1),
              der(E2,DE2).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%To simplify the resulting derivative we represent polinomials
%as lists of the form [...[Ci,Ni]...] where [Ci,Ni] corresponds
%to the term Ci*x^Ni. Polinomials, written in this form will be 
%called l-polynomials. The derivative DF of F computed
%by der(F,DF) will be translated into equivalent l-polynomial,
%written in canonical form and trnaformed back into the term form.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%transform(T,[[C1,N1],...,[Ck,Nk]]) implies that
%T = C1*x^N1 +...+ Ck*x^Nk. 
%
%type: T - polynomial, C - integer, N - nonnegative integer.
%mode: transform(+,?).
%A list L = [[C1,N1],...,[Ck,Nk]]) such that T = C1*x^N1 +...+ Ck*x^Nk
%will be called list-representation of T. Change of representation
%will be used to simplify the derivative. 

transform(C,[[C,0]]) :-
     integer(C).
transform(x,[[1,1]]).
transform(A*B,L) :-
     transform(A,L1),
     transform(B,L2),
     multiply(L1,L2,L).
%transform(A^N,[[C,M]]) :-
%     transform(A,[[C1,M1]]),
%     power(C1,N,C),
%     M is M1 * N.
transform(A^N,L) :-
      transform(A,L1),
      get_degree(L1,N,L).
transform(A+B,RT) :- 
     transform(A,RA),
     transform(B,RB),
     append(RA,RB,RT).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%multiply(L1,L2,L) L is the product of L1 and L2
%type: L1,L2,L - l-lists
%mode: multiply(+,+,-)

multiply_one(_,[],[]).
multiply_one([C1,N1],[[C2,N2]|R],[[C,N]|T]) :-
     C is C1*C2,
     N is N1+N2,
     multiply_one([C1,N1],R,T).

multiply([],_,[]).
multiply([H1|T1],T2,T) :-
     multiply_one(H1,T2,R1),
     multiply(T1,T2,R2),
     append(R1,R2,T).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%get_degree(L1,N,L) L is L1^N
%type: L1,L - l-lists, N - nonnegative integer
%mode: get_degree(+,+,-)

get_degree(L1,0,[[1,0]]).
get_degree(L1,1,L1).
get_degree(L1,N,L) :-
     N > 1,
     M is N-1,
     get_degree(L1,M,L2),
     multiply(L1,L2,L).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%add_similar(L1,L2) implies that L2 is the result of 
%adding up similar terms of L2.
%type: L1 and L2 are l-polynomials.
%mode: add_similar(+,?)

add_similar([],[]).
add_similar([[C1,N]|T],S) :-
     append(A,[[C2,N]|B],T),
     C is C1+C2,
     append(A,[[C,N]|B],R),
     add_similar(R,S).

add_similar([[C,N]|T],[[C,N]|ST]) :-
     not_in(N,T),
     add_similar(T,ST).


not_in(N,[]).
not_in(N,[[]]).
not_in(N,[[_,M]|T]) :- 
               N \== M,
               not_in(N,T).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%remove_zero(L1,L2) iff L2 is obtained from L1 by removing
%zero terms [0,N].
%type: L1,L2  l-polynomilas
%mode: remove_zero(+,-)

remove_zero([],[]).
remove_zero([[0,_]|T],T1) :-
     remove_zero(T,T1).
remove_zero([[C,N]|T],[[C,N]|T1]) :-
     C \== 0,
     remove_zero(T,T1).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%back_to_terms(T,L) implies that T is a term-representation 
%of L 
%type: T polynomial, L l-polynomial
%mode: back_to_terms(?,+)

back_to_terms(x,[[1,1]]).
back_to_terms(C,[[C,0]]) :-
     integer(C).
back_to_terms(C*x^N,[[C,N]]):-
     N \== 1,
     C \== 1.
back_to_terms(x^N,[[1,N]]):-
     N \== 1.
back_to_terms(C*x,[[C,1]]):-
     C \== 1.
back_to_terms(x,[[1,1]]).
back_to_terms(F+T,[L1|L]) :-
     back_to_terms(T,[L1]),
     back_to_terms(F,L).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%simplify(P,SP) iff SP is a canonical form of a polynomial P
%type: P, SP - polynomials
%mode simplify(+,?)

simplify(P,SP) :- 
     transform(P,TP),
     add_similar(TP,S),
     remove_zero(S,S1),
     my_sort(S1,S2),
     back_to_terms(SP,S2).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Library

%power(X,M,P)
power(X,0,1) :- 
     X \== 0.
power(X,M,P) :-
     X \== 0,
     M > 0,
     M1 is M - 1,
     power(X,M1,P1),
     P is P1 * X.

%my_sort(+,-)
my_sort([X|Xs],Ys) :-
     my_sort(Xs,Zs),
     insert(X,Zs,Ys).
my_sort([],[]).

insert(X,[],[X]).
insert(X,[Y|Ys],[Y|Zs]) :-
     less(Y,X),
     insert(X,Ys,Zs).
insert(X,[Y|Ys],[X,Y|Ys]) :-
     lesseq(X,Y).

less([_,N1],[_,N2]) :-
     N1 < N2.

lesseq([_,N1],[_,N2]) :-
     N1 =< N2.

%\end{verbatim}
%\end{document}