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.
- 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:
(setq *ops* '(
( (= ?x (+ ?y ?z)) (= (- ?x ?y) ?z) )
( (= ?x (+ ?y ?z)) (= (- ?x ?z) ?y) )
- 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.
- Write a function (failure? s) to test whether s is a
failure state. Actually, failure? could just return nil.
- 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.
- Write a function (apply-op op s) to apply the rewrite rule
op to the equation s.
- Write a function (apply-ops oplist s) to apply each of the
rewrite rules in oplist successively to s.
- 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
(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
- 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.)
- 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.)
- 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.)
- 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
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?
'((= g 9.80665)
(= h (* (/ g 2) (expt time 2)))
(= v (* g time)) )
'v '((h . 125)) )
(solve-eqn-set *circle* 'circumference '((area . 20)))