Symbolic Algebra and Patterns

Due: Friday, September 21, 2007.

In this assignment, we will solve algebra problems by using rewrite rules as operators in a state-space search. We will also extend the power of our symbolic algebra programs.

You may use in this assignment the functions that you have written previously.

Write a function (solve e v) that attempts to solve the equation e for variable v (we assume that v occurs at most once in e).
This version of solve will do the same thing as the previous version, but will do it using the sss program and pattern matcher. The sss program is defined in the file miscan.lsp; you may copy it, or put (load "/projects/cs343/miscan.lsp") near the top of your file.
1. Write a set of rewrite rules that express the legal algebraic transformations of equations. Each rewrite rule is a list of an input pattern and an output pattern:
```
(defvar *goal*)
(defvar *ops*)
(setq *ops* '(
  (  (= ?x (+ ?y ?z))   (= (- ?x ?y) ?z)  )
  (  (= ?x (+ ?y ?z))   (= (- ?x ?z) ?y)  )
     ... ))
```
2. Write a function (applicable? op s) to test whether an operator op is applicable to a state s. In this case, s is an equation and op is a rewrite rule.
3. Write a function (failure? s) to test whether s is a failure state. Actually, failure? could just return nil.
4. Write a function (goal? s) to test whether equation s is a goal. Assume that the global variable *goal* has been set to the goal variable, and that an equation is a goal if it has that variable as either side.
5. Write a function (apply-op op s) to apply the rewrite rule op to the equation s.
6. Write a function (apply-ops oplist s) to apply each of the rewrite rules in oplist successively to s.
7. Write the function (solve e v) so that it sets the *goal* variable, calls the sss function to find an operator sequence, uses apply-ops to get the goal equation, and reverses the sides of the result if needed to put the goal variable on the left.
Write a function (solve-val e alist) that will find the numeric value of the rhs of the equation e given the alist of values of all the variables in the rhs. This is a one-line function.
```
(solve-val '(= f (* m a)) '((a . 3) (m . 2)))   =   6
```
Students in introductory physics courses often do their homework problems by searching for an equation that relates the variables whose values are given and the desired variable. Solving this equation for the desired variable and plugging in the values gives the answer.
Write a function (find-eqn eqns var alist) that will look through a list of equations eqns and return the first equation that relates the variable var and the variables defined in the alist.
```
(find-eqn *formulas* 'a '((f . 8) (m . 2)))   =   (= A (/ F M))
```
Write a function (solve-eqns eqns var alist) that will find and solve an equation to give the value of var given the values defined in the alist.
```
(solve-eqns *formulas* 'a '((f . 8) (m . 2)))   =   4
```
Use your function solve-eqns to solve the following problems given the formulas in *formulas*, defined in the file formulas.lsp:
1. A pebble is dropped off the UT tower and hits the ground after 4 seconds. What is the height of the tower in meters? (Find h0 given h = 0, t = 4.)
2. A car accelerates from zero to 60 mph (88 ft/s) in 8 seconds. What is its acceleration? (Find a given v = 88, t = 8.)
3. A capacitor is charged through a resistance of 10K ohms using a 6 volt battery. It reaches 3 volts after 5 seconds. What is its capacitance? (Find c given v = 3, v0 = 6, r = 10000, t = 5.)
4. A ladder 10 ft long leans against a wall. The foot of the ladder is 6 ft from the wall. How far up the wall is the top of the ladder? (Find b given c = 10, a = 6.)
A physics or mathematical principle often involves an equation set consisting of multiple equations using the same variables.
Write a function (solve-eqn-set eqns var alist) that will attempt to find the value of var given the values defined in the alist and the equations eqns.
Your function should look through the equation set to find equations for which exactly one variable is undefined and the others are defined in alist; find the value of that variable and add it to the alist. Continue this process until the desired variable var is found or until no further progress is made.
Some equation sets are defined in the file formulas.lsp
Example: A stone is dropped from a height of 125 meters. With what velocity does it hit the ground?
```
(solve-eqn-set
  '((= g 9.80665)
    (= h (* (/ g 2) (expt time 2)))
    (= v (* g time)) )
  'v '((h . 125)) )

(solve-eqn-set *circle* 'circumference '((area . 20)))
```