CS 307: 8. Symbolic Algebra
Due: Friday, October 26, 2001.
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)).
- Write a recursive function (vars f) that produces a
list of the variables in the formula or expression f. Use auxiliary
functions as needed.
(vars 'a) => (a) (vars '(+ a a)) => (a)
(vars '(= a b)) => (a b) (vars '(+ a 2)) => (a)
- Write a (one-line!) function (evalexp exp vals) that
evaluates an expression exp given an association list vals
of values for the variables in the expression.
(evalexp '(+ b a) '((a . 3) (b . 4))) => 7
- Write a (one-line!) function (substin f1 f2) that creates
a new equation by substituting the definition of a variable, given by
equation f2, into equation f1.
(substin '(= s (* 0.5 (* a (expt t 2))))
'(= a (/ f m)))
=> (= s (* 0.5 (* (/ f m) (expt t 2))))
- Write a recursive function (solve e v) that attempts to
solve the equation e for variable v, which we assume
occurs at most once in e. The basic idea of solve is to
test for equations that are already solved or unsolvable (base cases);
otherwise, solve will search for a solution by applying laws of
algebra. solve is a kind of tree recursion -- not recursion
on car and cdr, but recursion on the applicable
operators (transformations of the input formula into new formulas).
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).
- If the left-hand side (lhs) of e is v, return e.
(solve '(= f (* m a)) 'f) => (= f (* m a))
- If the right-hand side (rhs) of e is v, return e
with its arguments reversed.
(solve '(= (* m a) f) 'f) = (= f (* m a))
- If the rhs is not v and not a list, return #f.
- If the rhs of e is a list (i.e. an operation), try to solve
the equation by applying algebraic
laws, 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 to give
x - y = - z and then negate both sides 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: #f
(solve '(= (+ x z) y) 'y) ; second try: succeeds
=> (= y (+ x z))
Demonstrate that you can solve the following equations for any of their
variables. These are defined in the file formulas.scm .
(= 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))))))
The solve function can be written in two different ways:
- Write code to create new equations from the existing one,
using list operations.
- Use patterns to transform the existing equation into new ones.
You may use the code in the file patmatch.scm if you wish.
- Write a function (make-fn fn e var) that will create and
define a Scheme function named fn to compute the value of the
variable var using the equation e. The equation e
should be solved for the desired variable; the other variables in the
equation should be arguments of the function. Use eval to evaluate
(make-fn 'find-h0 '(= h (- h0 (* 4.94 (expt t 2)))) 'h0)
=> (define (find-h0 h t) (+ h (* 4.94 (expt t 2))))
- Students in beginning physics courses
often solve homework problems by searching through the
book for an equation that relates the desired variable
and the variables whose values are given.
Define a function (solveit equations var values) where
equations is a list of equations, var is a variable
whose value is desired, and values is an association list of variables
with known values. Search the list equations to find one
that relates these variables. Solve the equation for the
desired variable and find its value.
(solveit formulas 'm '((f . 10) (a . 2))) => 5
Use the equations in question (4) and solve the following problems:
- 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.)