Submission directions: Please turn in both printed and electronic copies of your code. The print submission is due in class on the due date above. You may e-mail the electronic copies to Keunwoo (klee@cs) anytime the same day. For full credit, you must follow the submission guidelines.
Write and test a set of Scheme functions to do algebraic simplification of arithmetic expressions. You should perform the following simplifications. In the rules below x, y, and z are arbitrary expressions. These rules are given in infix notation, but your Scheme functions should manipulate expressions using Scheme's expression syntax.
; Addition
a+b => value of a+b if a and b are numbers
0+x => x
x+0 => x
; Multiplication
a*b => value of a*b if a and b are numbers
0*x => 0
x*0 => 0
1*x => x
x*1 => x
; Exponentiation
a**b => value of a**b if a and b are numbers
x**0 => 1
1**x => 1
x**y * x**z => x**(y+z)
(x**y)**z => x**(y*z)
Test your function on the following inputs, plus others if
appropriate. The correct output is also shown here. (Note:
expt is simply the Scheme function for exponentiation;
(expt x y) is equivalent to x y.)
(simplify '(+ 2 3)) => 5
(simplify '(* x 0)) => 0
(simplify '(* 1 (+ (+ x 0) (* x 0)))) => x
(simplify '(expt (* x 2) 0)) => 1
(simplify '(* (expt x 2) (expt x 5))) => (expt x 7)
(simplify '(* (expt (+ x 1) 2) (expt (+ (* 1 x) (+ 1 0)) 5))) =>
(expt (+ x 1) 7)
(simplify '(expt (expt x 2) (+ 3 4))) => (expt x 14)
For the rule
x**y * x**z => x**(y+z)you should just check whether the two x expressions on the left hand side of the arrow are equal (using Scheme's equal? predicate); you don't have to build in knowledge of the commutative or associative laws.
You can also check that your simplifications are working correctly by giving the variables values and using eval on the original and simplified expressions. For example:
(define x 5) (define y 10) (eval '(* x (+ y 0)) user-initial-environment) => 50 (eval (simplify '(* x (+ y 0))) user-initial-environment) => 50(Make sure you undestand why this works.)
To help you get started, some Scheme functions that perform the simplifications for + and * are in the file ~borning/341/simplify.scm on tahiti. You can copy this file to your own directory, try it on the problems not involving expt to make sure it's working, and edit as needed.
Your program should be written in a purely functional style, with no side effects. (The starting file mentioned above is in this style.)