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).