Symbolic Algebra

Due: Friday, September 14, 2007.

All computer languages can perform numerical computations. Lisp can also manipulate formulas symbolically. We will represent equations in Lisp notation; for example, the equation f = m * a is written (= f (* m a)). We will assume that all operations are unary or binary.

Write access functions that retrieve the op (operator), lhs (left-hand side) and rhs (right-hand side) of an expression list.

Write a recursive function (vars f) that produces a list of the variable symbols in the formula or expression f. Note that some symbols (such as nil and pi) are constants; you can test for this using constantp.

   (vars '())       =>  NIL or ()  (vars 'a)        =>  (a)
   (vars 'pi)       =>  NIL or ()
   (vars '(sqrt x)) =>  (x)        (vars '(+ a a))  =>  (a)
   (vars '(= a b))  =>  (a b)      (vars '(+ a 2))  =>  (a)

Write a recursive function (solve e v) that attempts to solve the equation e for variable v (we assume that v occurs at most once in e). The basic structure of solve is to test for base cases (equations that are already solved, or unsolvable); otherwise, solve will search for a solution by applying laws of algebra. solve is a tree recursion over all algebraic transformations of the input formula, until the desired formula is found.
solve will return nil if it fails, or a formula with v on the lhs.
1. If the left-hand side (lhs) of e is v, return e.
```
   (solve '(= f (* m a)) 'f)  =>  (= f (* m a))
```
2. If the right-hand side (rhs) of e is v, return e with its arguments reversed.
```
   (solve '(= (* m a) f) 'f)  =>  (= f (* m a))
```
3. If the rhs is not v and not a list (consp), return nil.
4. If the rhs of e is a list (i.e. an operation), try to solve the equation by applying algebraic laws, each of which will make a new equation by moving things to the left side. Then try to solve that equation. For binary operators, there will be two possibilities, both of which must be tried.
  For example, given the original equation (= x (- y z)), we could (a) add z to both sides to give (= (+ x z) y), or (b) subtract y from both sides and negate to give (= (- y x) z) (these two operations can be combined as a single transformation).
```
   (solve '(= x (- y z)) 'y)
      (solve '(= (- y x) z) 'y)   ; first try:  nil
      (solve '(= (+ x z) y) 'y)   ; second try: succeeds
    =>  (= y (+ x z))
```
Hint: first write the solve function so that it handles only the base cases and the + operator. Do (trace solve) so you can observe how it works on more complex expressions.
You should handle the operators + - * / sqrt exp log and (expt x 2). The operator - can be either unary (having only one argument, i.e. minus) or binary (having two arguments, i.e. difference), which must be treated differently. We will assume that all other operators will have a fixed number of arguments (either one or two).
Demonstrate that you can solve the following equations for any of their variables. These are defined in the file formulas.lsp .
```
   (= s (* 0.5 (* a (expt t 2))))
   (= s (+ s0 (* v t)))
   (= a (/ f m))
   (= v (* a t))
   (= f (/ (* m v) t))
   (= f (/ (* m (expt v 2)) r))
   (= h (- h0 (* 4.94 (expt t 2))))
   (= c (sqrt (+ (expt a 2) (expt b 2))))
   (= v (* v0 (- 1 (exp (/ (- t) (* r c))))))
```