CSE 413 -- Assignment 2 -- Scheme Programming

Due at the beginning of lecture, Monday, April 19, 1999.  You should hand in

• A printout of the Scheme source code for your program.
• A console transcript demonstrating that your program works properly on a variety of input data. If you implement any extensions to the basic problem, be sure to demonstrate them.

Symbolic algebra was one of the original application areas for Lisp, the ancestor of Scheme. In this exercise, you will solve symbolic equations in one variable. Write a Scheme function solve that takes a variable var to be solved for and an eqn as arguments. The function should return another equation representing the solution to the first. In the solution equation, var should appear by itself on the left-hand-side of the equation.

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 /. You can assume that each of these functions 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.

Optional Extra Credit Extensions

There are a number of ways the basic assignment can be extended. Some modest number of points of extra credit will be given for extensions. (The number of points will depend on what you do, of course.) Here are some suggestions. If you do an extra credit version, please include comments explaining exactly what you've done, and include suitable test cases.

• Check the input to make sure that it is well-formed. Otherwise call error.
• Do some simplification of your answer, if possible.
• Deal with possible division by 0 by including conditions in your result that must be true for the answer to be correct. For example, given

  (solve 'x '(= (* a x) 10))

  return

  ((= x (/ 10 a)) if (/= a 0))

• Handle a wider range of equations. For example, you might handle arbitrary linear equations (which might include more than one occurrence of the unknown), quadratics, or equations with additional functions (e.g. sqrt, trig, exponentiation, or log).
• Allow the functions +, -, *, and / to take an arbitrary number of arguments, as in Scheme normally.
• Do some fancier output -- for example, output a latex source file using latex's math mode giving the original and solved equations.