CSE 341 -- Assignment 8 -- Prolog Project

November 17, 1995
Due in quiz sections November 30, 1995

In Assignment 3 you wrote a Lisp function print-polynomial that accepted a Lisp s-expression representing a polynomial in a single variable as input, and printed it out in normal form. For this assignment, write a similar program in Prolog.

Since Prolog terms representing algebraic expressions print out just fine, you don't need to write the printing part -- just produce a legal Prolog term representing the symbolic polynomial in polynomial normal form.

Specifically, write a rule

polynomial_form(Expr,Symbol,Normalized) When you invoke the rule, Expr should be a ground term representing a legal symbolic expression built up from a single symbol, numbers, and the functors +, -, *, and ^ (exponentiation). As before, the power in an exponentiation is restricted to be a non-negative integer. Symbol should be an atom representing the single variable in Expr. Normalized should be a variable when you call the rule; if the goal succeeds, Normalized should be unified with a term representing the polynomial in normal form. If the input is bad, the rule should fail.

Examples:

polynomial_form( (x+1)^2,x,N ) should succeed, unifying N with x^2 + 2*x + 1. polynomial_form( (x+1+3)*3*x*x,x,N ) unifies N with 3*x^3 + 12*x^2 polynomial_form( (x+1)*(x-1),x,N ) unifies N with x^2 - 1 polynomial_form( (x+x)*0+4,x,N ) unifies N with 4 polynomial_form( 0,x,N ) unifies N with 0 polynomial_form( x+3-3,x,N ) unifies N with x polynomial_form( x-3-x,x,N ) unifies N with -3 polynomial_form( (x+1)^10,x,N ) unifies N with x^10+10*x^9+45*x^8+120*x^7+210*x^6+252*x^5+210*x^4+120*x^3+45*x^2+10*x+1 polynomial_form( x+y,x,N ) fails polynomial_form( x/3,x,N ) fails polynomial_form( x^0.5,x,N ) fails Note that the symbol is a Prolog atom (lower case), not a Prolog variable! (If you try to use a Prolog variable, it's going to unify with something and you are likely to have problems getting your rule to work correctly.)

To help you get started, the file ~borning/341/polynomial.pl on mscc.ms contains the sample goals to run, and much of the program. The main rule is:

polynomial_form(Expr,Symbol,Normalized) :- expr_to_terms(Expr,Symbol,Terms), simplify(Terms,STerms), terms_to_expr(STerms,Symbol,Normalized). You need to write rules for expr_to_terms; the others are in the file. Also there are a set of goals pre-defined to run the required tests. (You can modify the existing code in any way you wish, or start from scratch. You may also want to look back at your solution to the Lisp project or to Andy's solution.)