CSE 413 Autumn 2006

Assignment 3 -- Symbolic Algebra

Symbolic algebra was one of the original application areas for Lisp, the ancestor of Scheme. In this part of the assignment, write a function that solves symbolic equations in one variable. Function solve should have two arguments: a variable var and an equality eqn. The result of (solve var eqn) should be another equality where var appears alone on the left and whose right argument is the solution of the original equation in terms of that variable.

The top level of the input equation eqn should be a list of the form (= exp1 exp2). The two expressions exp1 and exp2 should be legal Scheme expressions formed from atoms, numbers, and function calls involving +, -, *, and / (only). You should assume that each of these functions is binary - has exactly two arguments. You don't need to worry about division by 0.

If there is exactly one occurrence of var in eqn, return the solution. Otherwise, return the atom TOO-HARD. Except for checking for the right number of occurrences of the unknown, you can assume the input is well-formed.

Test your solve function on a number of examples to demonstrate that it is working correctly, including the following. (The answers are given on the next line in each case.)

(solve 'x '(= 3 x))
(= x 3)

(solve 'x '(= (+ x 3) (* 8 y)))
(= x (- (* 8 y) 3))

(solve 'y '(= (+ (+ (* a x) (* b y)) k) 0))
(= y (/ (- (- 0 k) (* a x)) b))

(solve 'x '(= y (/ 1 x)))
(= x (/ 1 y))

(solve 'x '(= (+ (+ (* a (* x x)) (* b x)) c) 0))
TOO-HARD

(solve 'y '(= y (* 2 y)))
TOO-HARD

(solve 'x '(= (* 2 (- 3 x)) (+ y z)))
(= x (- 3 (/ (+ y z) 2)))

Your solution should be written completely in a functional style -- you may not use functions with side effects, such as set!, set-car!, and so forth. Your code should be well-commented. If appropriate, create "data structures" using functions, like the ones we created for the expression tree problems in the previous assignment.  (For example, your code could be much easier to read if you define functions to extract the operator, left operand, and right operand from a binary expression or equation.)

What to Hand In

Turn in a copy of your Scheme source files using this online turnin form.

Paper Submission

Hand in the following:

1. A printed copy of your Scheme code.
2. A printout showing the transcript of the Scheme session demonstrating the results produced by your equation solver for suitable test cases.  This should contain enough to show that your code works, but no more than necessary to do that. Part of your grade will be determined by the quality of the test cases you use for this.  (Don't worry if there are some minor typos in the transcript - just draw a line through anything we should ignore.)