CS 381K: Symbolic Differentiation

Due: September 24, 2007.

Introduction

A symbolic differentiation program finds the derivative of a given formula with respect to a specified variable, producing a new formula as its output. In general, symbolic mathematics programs manipulate formulas to produce new formulas, rather than performing numeric calculations based on formulas. In a sense, symbolic manipulation programs are more powerful: a formula provides answers to a class of problems, while a numeric answer applies only to a single problem.

Symbolic differentiation makes a good exercise in Lisp programming because it is easy to do and takes advantage of unique features of Lisp. Symbolic differentiation is an easy problem in Lisp because it can be solved using the divide and conquer strategy (also called problem reduction search):

  1. If the problem to be solved is an easy problem, solve it at once.
  2. If the problem to be solved is a hard problem,
    1. Break the problem into smaller subproblems.
    2. Use the problem-solver itself, recursively, to solve the subproblems.
    3. Combine the solutions of the subproblems to make a solution for the larger problem.
Symbolic differentiation is guaranteed to be solved by this strategy because:
  1. Solutions to the subproblems are guaranteed to provide a solution to the larger problem.
  2. The subproblems are always smaller (less difficult) than the original problem; this guarantees that the solution process will terminate.
  3. The subproblems are independent; that is, the solution to one subproblem cannot interfere with the solution to another subproblem.
For this exercise, write a function named deriv with arguments form (the formula to be differentiated) and var (the variable with respect to which the derivative is taken). form is written in Lisp notation, that is, a mathematical operation is written as a Lisp list with the function name first and arguments following. Assume that the usual Lisp operators (+ - * /) are used, as well as mathematical functions (sqrt, log, exp, sin, cos, and tan). expt raises its first argument to the power specified by its second argument. For simplicity, we will assume that all of the binary algebraic operators have exactly two arguments.

The following rules of differential calculus apply; the notation used is d/dx[form] where x is the variable with respect to which the derivative is taken and form is the formula whose derivative is desired.

  1. d/dx[c] = 0 , where c is a numeric constant.
  2. d/dx[x] = 1
  3. d/dx[v] = 0 , where v is a variable other than x.
  4. d/dx[u + v] = d/dx[u] + d/dx[v]
  5. d/dx[u - v] = d/dx[u] - d/dx[v]
  6. d/dx[-v] = - d/dx[v]
  7. d/dx[u * v] = u * d/dx[v] + v * d/dx[u]
  8. d/dx[u / v] = (v * d/dx[u] - u * d/dx[v]) / v2
  9. d/dx[uc] = c * u(c - 1) * d/dx[u] , where c is constant. (We will only consider this case. The Lisp function (expt x n) raises x to the power n.)
  10. d/dx[sqrt(u)] = (1/2) * d/dx[u] / sqrt(u)
  11. d/dx[log(u)] = (d/dx[u]) / u
  12. d/dx[exp(u)] = exp(u) * d/dx[u]
  13. d/dx[sin(u)] = cos(u) * d/dx[u]
  14. d/dx[cos(u)] = - sin(u) * d/dx[u]
  15. d/dx[tan(u)] = (1 + tan(u)2) * d/dx[u]
Write your functions in such a way that the main function, deriv, solves the easy cases directly; for each more complex case, deriv should determine what the operator is and call an appropriate function to take the derivative of a formula involving that operator. (It may be convenient to let one function handle multiple operators whose derivatives are similar.)

Test your program on the following test cases, and on others which you make up. In these examples, the derivative is taken with respect to x. The function expt is used for "raised to the power".

  1. x
  2. 3
  3. y
  4. x+7
  5. x*5
  6. 5*x
  7. x3 + 2*x2 - 4*x + 3
  8. sqrt(x2 + 2)
  9. log((1 + x)3)

Values of Derivatives

Write a function deriv-val, with arguments form, var, and val, which will take the derivative of form with respect to var and return the numerical value of the derivative when var has the value val. We will assume that any variables other than var have values assigned to them outside the call to deriv-val. Test your function on the above examples with the value 7 for x. Note: deriv-val is a very short function.

Symbolic Simplification

The values returned by deriv may be mathematically correct, but not very useful if they contain extraneous algebra. It is apparent that in addition to the deriv program, we need a symbolic simplifier that can simplify the result using well-known mathematical identities. In general, algebraic simplifiers may be very complex. However, it is easy to catch some common cases at the point of generation.

Simplification by Programs

Write functions s+, s-, sminus, s*, and s/ to simplify expressions whose top operator is +, -, unary -, *, and /, respectively. Each of these functions will have two arguments, lhs and rhs (left-hand side and right-hand side). If no simplification can be performed, each function will return as its value the list (op lhs rhs), where op is the operator associated with the simplifier function. In certain cases, a simpler form can be returned. For example, if lhs and rhs are both numbers, the operation can be performed at once (this is called constant folding). You can also make use of mathematical identities such as x+0=x, x*0=0, x*1=x, etc. Make your derivative functions use the simplifier functions in constructing their answers.

Note that it is often easiest to test Lisp functions individually on small test cases before testing them as part of a larger system. For example, the following test cases might be used for s+:

  1. (s+ 2 3) = 5
  2. (s+ 'a 'b) = (+ A B)
  3. (s+ 'x 0) = X
  4. (s+ '(- x) 'x) = 0
The last example above suggests that a really good simplifier would be required to cover a lot of cases. Can the job of writing a simplifier ever be finished? That is, is it possible to write a simplifier that will simplify any arithmetic formula into its simplest form? Turn in a paragraph discussing this question.

Simplification by Patterns

Programs such as s+ are a procedural representation of knowledge. Sometimes it is preferable to have a declarative representation of knowledge as a set of rules or transformations; this can be better because it is possible to do other things with declarative knowledge (e.g., justify a conclusion by listing the rules used), whereas procedural knowledge usually is not suitable for introspection.

Simplification can be done procedurally (by expanding programs such as s+ to handle more cases), by pattern matching (representing simplification transformations as patterns), or both. The procedural option is more efficient for simple patterns such as (+ x 0) that are frequently generated. For larger patterns, the procedural approach may result in large and error-prone code; a pattern-matching approach is probably better for these. The file patmatch.lsp contains some simple pattern-matching and transformation functions. Study these functions and try using patterns to simplify the output of your deriv function.

Look at the output of your deriv function to see whether it could be simplified to produce a better result. Use programs and/or patterns to improve the quality of the output; the quality of output will be a grading criterion.

Simplification by Itself

The simplification functions written for this assignment perform symbolic simplification at the point of generation of formulas, that is, before the formulas have actually been constructed. In an application like symbolic differentiation, where much useless algebra is generated, it makes sense to throw away the useless items as early as possible, rather than generating big formulas and then paring them down. This avoids unnecessary conses, which is a good idea since cons is expensive. However, it may still be nice to have a simplify function that can simplify a formula that already exists. Write such a simplify function that will traverse a given formula, applying the appropriate simplification methods that you already have, to create a simplified formula. simplify should be recursive and not too large; it is somewhat analogous to the copy-tree function in Common Lisp.

References

  1. Pavelle, R., Rothstein, M., and Fitch, J., ``Computer Algebra'', Scientific American, Dec. 1981, p. 136.
  2. Rayna, Gerhard, REDUCE Software for Algebraic Computation, Springer-Verlag, 1987.
  3. Wolfram, Stephen, Mathematica, Addison-Wesley, 1988.
  4. SIGSAM Bulletin, ACM, 11 West 42nd Street, New York, NY 10036.
  5. Symbolic math web page, http://www.SymbolicNet.org