CSE 341 -- Assignment 8 Sample Solution
This solution is also stored on mscc on ~borning/341/polynomial-solution.pl
/**************************************************
Sample solution to Assignment 8, Polynomial Normal Form program in Prolog.
The problem is to write a Prolog rule, polynomial_form, that takes a
standard Prolog term representing a polynomial in one variable, and the
variable, and that unifies the third argument with a term representing the
polynomial in normalized form.
(This solution includes the fixes Regan Pelton e-mailed to the class.)
**************************************************/
/* sample goals */
all_goals :-
go1(N1), write('goal 1 result: '), write(N1), nl,
go2(N2), write('goal 2 result: '), write(N2), nl,
go3(N3), write('goal 3 result: '), write(N3), nl,
go4(N4), write('goal 4 result: '), write(N4), nl,
go5(N5), write('goal 5 result: '), write(N5), nl,
go6(N6), write('goal 6 result: '), write(N6), nl,
go7(N7), write('goal 7 result: '), write(N7), nl,
go8(N8), write('goal 8 result: '), write(N8), nl,
/* now try the goals that should fail (\+ means not) */
\+ go9(_), write('go9 failed'), nl,
\+ go10(_), write('go10 failed'), nl,
\+ go11(_), write('go11 failed'), nl.
go1(N) :- polynomial_form( (x+1)^2,x,N ).
go2(N) :- polynomial_form( (x+1+3)*3*x*x,x,N ).
go3(N) :- polynomial_form( (x+1)*(x-1),x,N ).
go4(N) :- polynomial_form( (x+x)*0+4,x,N ).
go5(N) :- polynomial_form( 0,x,N ).
go6(N) :- polynomial_form( x+3-3,x,N ).
go7(N) :- polynomial_form( x-3-x,x,N ).
go8(N) :- polynomial_form( (x+1)^10,x,N ).
go9(N) :- polynomial_form( x+y,x,N ).
go10(N) :- polynomial_form( x/3,x,N ).
go11(N) :- polynomial_form( x^0.5,x,N ).
/* The main rule is polynomial_form. This rule uses three auxiliary
rules: expr_to_terms, simplify, and terms_to_expr. (This solution is adapted
from the Lisp sample solution.)
expr_to_terms takes an expression produces a list of coefficient-exponent
pairs. (We are using the word "terms" here to mean the algebraic terms,
rather than logic programming terms.) simplify simplifies this list,
sorting the terms, combining terms with like exponents, and deleting terms
with a coefficient of 0. Finally, terms_to_expr takes a list of
coefficient-exponent pairs, sorted by exponent and simplified, and puts it
back into standard expression form.
Lists of terms are represented as: [term(C1,E1),term(C2,E2), ...] where the
Cs are coefficients and the Es are exponents. The Es will all be
non-negative integers.
For example, the polynomial 2*x^4 + x^2 + 3*x + 5 would be represented as
[term(2,4),term(1,2),term(3,1),term(5,0)]
*/
polynomial_form(Expr,Symbol,Normalized) :-
expr_to_terms(Expr,Symbol,Terms),
simplify(Terms,STerms),
terms_to_expr(STerms,Symbol,Normalized).
/* expr_to_terms takes an expression and produces a list of
coefficient-exponent pairs */
/* rule to convert a number N */
expr_to_terms(N,Symbol,[term(N,0)]) :- number(N).
/* rule to convert a single variable that is the designated variable for the
polynomial (it has an implicit coefficient of 1) */
expr_to_terms(Symbol,Symbol,[term(1,1)]).
/* rule to convert a sum */
expr_to_terms(E1+E2,Symbol,L) :-
expr_to_terms(E1,Symbol,L1),
expr_to_terms(E2,Symbol,L2),
append(L1,L2,L).
expr_to_terms(E1-E2,Symbol,L4) :-
expr_to_terms(E1,Symbol,L1),
expr_to_terms(E2,Symbol,L2),
negate(L2,L3),
append(L1,L3,L4).
expr_to_terms(E1*E2,Symbol,L3) :-
expr_to_terms(E1,Symbol,L1),
expr_to_terms(E2,Symbol,L2),
mult_lists(L1,L2,L3).
expr_to_terms(E^N,Symbol,L) :-
integer(N),
N>=0,
expr_to_terms(E,Symbol,Terms),
expt(Terms,N,Symbol,L).
negate([],[]).
negate([term(Coeff,Exp)|Terms],[term(NegCoeff,Exp)|NTerms]) :-
NegCoeff is 0 - Coeff,
negate(Terms,NTerms).
mult_lists([],L,[]).
mult_lists([T|Terms],L2,L5) :-
mult_term_list(T,L2,L3),
mult_lists(Terms,L2,L4),
append(L3,L4,L5).
mult_term_list(T1,[],[]).
mult_term_list(T1,[T2|Ts],[T3|TTs]) :-
mult_terms(T1,T2,T3),
mult_term_list(T1,Ts,TTs).
mult_terms(term(C1,E1),term(C2,E2),term(C3,E3)) :-
C3 is C1*C2,
E3 is E1+E2.
expt(Terms,0,Symbol,[term(1,0)]).
expt(Terms,N,Symbol,L) :-
N>0,
N1 is N-1,
expt(Terms,N1,Symbol,L1),
mult_lists(Terms,L1,L).
/* Rules to simplify a list of terms. Sort the terms, combine terms with
like exponents, and omit terms with a coefficient of 0. */
simplify([],[]).
simplify([T|Ts],S2) :-
simplify(Ts,S1),
insert(T,S1,S2).
/* "insert" inserts a term into the proper place in a sorted list of terms,
adding coefficients of terms with equal exponents and dropping
terms with a coefficient of 0 */
/* always drop a term with a 0 coefficient */
insert(term(0,_),Ts,Ts) :- !.
/* rule to insert a term into an empty list of terms (if we get here the
coefficient isn't 0) */
insert(T,[],[T]).
/* rule to insert a term into a list, the first element of which has the
same exponent and cancelling coefficients (so drop the terms) */
insert(term(C1,E),[term(C2,E)|Ts],Ts) :-
0 is C1+C2, !.
/* rule to insert a term into a list, the first element of which has the
same exponent (so combine the terms -- we already decided they didn't
sum to zero) */
insert(term(C1,E),[term(C2,E)|Ts],[term(C3,E)|Ts]) :-
C3 is C1+C2.
/* rule to insert a term into a list (when the term has a bigger exponent
than any current term -- so put it at the head of the list */
insert(term(C1,E1),[term(C2,E2)|Ts],[term(C1,E1),term(C2,E2)|Ts]) :-
E1 > E2.
/* rule to insert a term somewhere in the list (after the head) */
insert(term(C1,E1),[term(C2,E2)|Ts],[term(C2,E2)|Us]) :-
E1 < E2,
insert(term(C1,E1),Ts,Us).
/* rules to convert a single term back into an ordinary Prolog expression
(taking into account the special case of exponents of 0 or 1 and
coefficients of 1). In addition, we separately return the sign (+ or -)
of the coefficient since this will be needed to assemble terms
correctly when a coefficient is negative. */
one_term(term(N,0),Symbol,N,+) :- N>=0, !.
one_term(term(N,0),Symbol,MinusN,-) :- N<0, MinusN is 0-N, !.
one_term(term(1,1),Symbol,Symbol,+) :- !.
one_term(term(-1,1),Symbol,Symbol,-) :- !.
one_term(term(N,1),Symbol,N*Symbol,+) :- N>0, !.
one_term(term(N,1),Symbol,MinusN*Symbol,-) :- N<0, MinusN is 0-N, !.
one_term(term(1,E),Symbol,Symbol^E,+) :- !. /* note that E>1 here */
one_term(term(-1,E),Symbol,Symbol^E,-) :- !.
one_term(term(N,E),Symbol,N*Symbol^E,+) :- N>0, !.
one_term(term(N,E),Symbol,MinusN*Symbol^E,-) :- N<0, !, MinusN is 0-N.
/* rules to convert a list of terms back to an ordinary Prolog expression */
/* these first rules handle the various special cases of 0 or 1 terms */
terms_to_expr([],Symbol,0).
terms_to_expr([term(N,0)],Symbol,N) :- number(N), !.
terms_to_expr([T],Symbol,E) :- one_term(T,Symbol,E,+).
terms_to_expr([T],Symbol,-E) :- one_term(T,Symbol,E,-).
/* Now the general caseof a list of terms. String them together using
the correct sign */
terms_to_expr([T1,T2|Ts],Symbol,E2) :-
one_term(T1,Symbol,E1,+),
aux_terms_to_expr(E1,[T2|Ts],Symbol,E2).
terms_to_expr([T1,T2|Ts],Symbol,E2) :-
one_term(T1,Symbol,E1,-),
aux_terms_to_expr(-E1,[T2|Ts],Symbol,E2).
/* aux_terms_to_expr is a helper rule to assemble the expression in the
proper order */
aux_terms_to_expr(E,[],Symbol,E).
aux_terms_to_expr(E,[T1|Ts],Symbol,E2) :-
one_term(T1,Symbol,E1,+),
aux_terms_to_expr(E+E1,Ts,Symbol,E2).
aux_terms_to_expr(E,[T1|Ts],Symbol,E2) :-
one_term(T1,Symbol,E1,-),
aux_terms_to_expr(E-E1,Ts,Symbol,E2).