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):
- If the problem to be solved is an easy problem, solve it at once.
- If the problem to be solved is a hard problem,
- Break the problem into smaller subproblems.
- Use the problem-solver itself, recursively, to solve the subproblems.
- 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:
- Solutions to the subproblems are guaranteed to provide a solution to
the larger problem.
- The subproblems are always smaller (less difficult) than the original
problem; this guarantees that the solution process will terminate.
- 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.
- d/dx[c] = 0 , where c is a numeric constant.
- d/dx[x] = 1
- d/dx[v] = 0 , where v is a variable other than x.
- d/dx[u + v] = d/dx[u] + d/dx[v]
- d/dx[u - v] = d/dx[u] - d/dx[v]
- d/dx[-v] = - d/dx[v]
- d/dx[u * v] = u * d/dx[v] + v * d/dx[u]
- d/dx[u / v] = (v * d/dx[u] - u * d/dx[v]) / v^{2}
- d/dx[u^{c}] = 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.)
- d/dx[sqrt(u)] = (1/2) * d/dx[u] / sqrt(u)
- d/dx[log(u)] = (d/dx[u]) / u
- d/dx[exp(u)] = exp(u) * d/dx[u]
- d/dx[sin(u)] = cos(u) * d/dx[u]
- d/dx[cos(u)] = - sin(u) * d/dx[u]
- 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".
- x
- 3
- y
- x+7
- x*5
- 5*x
- x^{3} + 2*x^{2} - 4*x + 3
- sqrt(x^{2} + 2)
- 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+:
- (s+ 2 3) = 5
- (s+ 'a 'b) = (+ A B)
- (s+ 'x 0) = X
- (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
- Pavelle, R., Rothstein, M., and Fitch, J., ``Computer Algebra'',
Scientific American, Dec. 1981, p. 136.
- Rayna, Gerhard, REDUCE Software for Algebraic Computation,
Springer-Verlag, 1987.
- Wolfram, Stephen, Mathematica, Addison-Wesley, 1988.
- SIGSAM Bulletin, ACM, 11 West 42nd Street, New York, NY 10036.
- Symbolic math web page,
http://www.SymbolicNet.org