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)).

  1. 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)
  2. 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
  3. 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))))
  4. 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).
    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, return #f.
    4. 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))
    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.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:

    1. Write code to create new equations from the existing one, using list operations.
    2. Use patterns to transform the existing equation into new ones. You may use the code in the file patmatch.scm if you wish.
  5. 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 the define.
       (make-fn 'find-h0 '(= h (- h0 (* 4.94 (expt t 2)))) 'h0)
          =>  (define (find-h0 h t) (+ h (* 4.94 (expt t 2))))
  6. 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:
    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.)