For this project you will write a scheme program to differentiate simple expressions. In case calculus is a distant memory, the rules for differentiation go something like:
Basic rules:
(d/dx) (constant) = 0
(d/dx) (x) = 1
(d/dx) (y) = 0 (if y does not depend on x)
(d/dx) (E1+ E2 + E3) = (d/dx)(E1) + (d/dx)(E2) + (d/dx)(E3) Differentiation of sums
(d/dx) (E1 * E2) = (E1 * (d/dx)(E2)) + (E2 * (d/dx)(E1)) Product rule
(d/dx) (xr) = r * (x)r-1 Power rule
More complex rules:
(d/dx) (ex) = ex
(d/dx) (ln x) = 1/x
(da/dx) = (da/db) * (db/dx) Chain rule
(d/dx) ((f(x))r) = r * (f(x))r-1 * (d/dx)(f(x)) Applying the chain rule.
(d/dx) (ef(x)) = ef(x) * (d/dx)(f(x)) Applying the chain rule.
Your program should be able to differentiate expressions containing constants, variables, sums with an arbitrary number of terms (+ E1 E2 E3 ... En), products with two terms (* E1 E2), and exponents of the form xy where y can be an integer or a variable other than x (expt x y). You can add additional operators for extra credit once you've implemented these basic requirements; see below for details.
You should implement the function (diff x E) to differentiate the expression E with respect to the variable x. Expressions should be represented in list format. That is,
| Formula | List Representation |
4 |
4 |
| 2x + 4 | (+ (* 2 x) 4) |
x + (x * x) |
(+ x (* x x)) |
3x + 4y + 6x3 |
(+ (* 3 x) (* 4 y) (* 6 (expt x 3))) |
Examples: (Your exact output may differ, but should be algebraically equivalent.)
> (diff 'x '4) => 0
> (diff 'x '(* 2 x)) => (+ (* 0 (* x)) (* 2 1)) (i.e. 2)
> (diff 'y '(* 2 y)) => (+ (* 0 (* y)) (* 2 1)) (i.e. 2)
> (diff 'x '(+ x (* x x))) => (+ 1 (+ (* 1 (* x)) (* x 1))) (i.e. 1 + x + x)
> (diff 'x '(expt x 4)) => (* 4 (expt x 3)) (i.e. 4 * x3)
Implementation:
You should implement function (diff v E) to differentiate the expression E with respect to the variable v. Note that v is an argument to diff that can be given any variable, not just 'v.
Your program must include functions to differentiate individual
kinds of
expressions (i.e., one function per top-level operator), and a dispatch
table that
function diff
will use to determine the appropriate sub-function to handle an expression,
based on the expression's operator. Use these fragments as
starting points for your code.
(define (diff-sum x E) ...) ; differentiate (+ x1 x2 ...) (define (diff-product x E) ...) ; (* x y) (define (diff-expt x E) ...) ; (expt x y);; Dispatch Table of supported operators. (define diff-dispatch (list (list '+ diff-sum) (list '* diff-product) (list 'expt diff-expt) ))
Be sure that the functions diff-sum, diff-product and diff-expt are defined before your dispatch table in your .scm file. To expand the program to differentiate other functions, you should only have to write an appropriate function to do the transformation, and then add an entry to the dispatch table with the operator symbol and the function name in a list. Once the code for diff is working on the basic cases, it should not need further changes to add additional kinds of expressions.
Your main diff function will look something like this:
;; Differentiate expression E w.r.t. x.
(define (diff x E)
(cond ((number? E) (diff-constant x E))
;; insert code here to handle the other base case - variables
...
(else ; insert code here to lookup the appropriate function in the
; dispatch table based on the operator in the expression,
; then call that function to differentiate the expression
(diff-func x E)))) ))
You should implement the functions: diff-sum, diff-product
and diff-expt. Your diff function should handle differentiation of
numbers and symbols (single variables such as x or y)
directly, as well as looking up and applying
the appropriate differentiating function for sums, products, expt and any other
functions you add.
Scheme Style:
Be sure to include the code above in your program exactly as written (with, of course, additions needed to implement the various functions). That is, you should use the function names diff-sum, diff-product etc with dashes (NOT underscores).
Good Scheme style is to define functions to abstract away from representation details. So instead of (car E) to access the operator of an expression, a better way of doing this is to define a function get-op to extract the operator from an expression, as follows:.
(define (get-op E) (car E))
You should define similar functions to access other parts of expressions, create various kinds of expressions, and so forth. Example: if you need to create a sum given a list of arguments, you could use a function like this:
(define (make-sum alist) (cons '+ alist))
If you include appropriate constructor and access functions, the code that differentiates expressions can be written in terms of
arguments and operators, not cars, cdrs and cadars,
which should make it much more readable.
Use higher-order functions and library functions when appropriate; don't implement special-purpose map functions when you can use library functions and functional parameters to do the job. For example, do not write your own specialized version of map that differentiates sums (instead you should use map to write diff-sum).
Testing:
Part of this assignment is to demonstrate that your program works using well-chosen test cases. A good set of test cases verifies basic and edge cases with a reasonably small set of carefully thought out test data, not just a large scattershot test with a bunch of random expressions, and comprehensively tests all of the functions and code. The examples listed above are only meant to illustrate how your program should work, they do not comprise a reasonable test suite! For full credit, you must 1) create a good suite of test cases and 2) write appropriate function(s) to simplify testing.
Here is one way you could do this. Define individual tests and a list that contains all of the tests.
(define test1 '(+ x 4)) (define test2 '(+ 9 8)) (define test-suite (list test1 test2))
Then define a function (runtest atest) that has a test as an
argument, and prints its argument and the result of applying (diff 'x arg)
to that argument all neatly formatted. Then you can use that function to run an
individual test, or map it over the list of tests to run all of them.
Example:
> (runtest test1) diff x (+ x 4) => (+ 1 0)
> (map runtest test-suite) diff x (+ x 4) => (+ 1 0) diff x (+ 9 8) => (+ 0 0) (#<void> #<void>) <--- ignore this, the return types of the 2 expressions evaluated while printing newlines. >
This makes it easy to re-run your test cases after modifying your program. Include the test cases and functions to process them in your Scheme file. Be sure that it is obvious how to run the tests, and also how to turn them off so we can run the code with additional tests.
Alternative: Instead of differentiating everything with respect to x, you might want a test cases to include both the expression and the differentiation variable. Example:
(define test10 '(x (+ x 4))) (define test11 '(y (+ x 4)))
Optional Extra Credit Extensions:
Be sure to have the original version of the program in perfect
working order before attempting any extra credit options.
Turn in your code in a file named hw3.scm once you
have the
basic part of the assignment working. After adding any extra
credit options you so
desire clearly label those extra credit
options added and resubmit your files via electronic
turnin using a different file name, hw3-extra.scm.
diff
on a large expression, the result can be rather hard to read. Write an algebraic simplifier that will make your
output easier to read. The simplifier should NOT be folded in with the basic diff
code. That is (diff x exp) should give an unsimplified answer.
Execution of (simplify (diff x exp)) would give the simplified code. An
example of simplification include "flattening" sums and products such as
converting: (+ x (+ 1 x) 1) to (+ x 1 x 1). Another simplification
is to remove the identity operand from expressions as in converting: (* 1 (+ x 0) x)
to (* (+ x) x) (or further, you get the idea). You
could also fold constants together or do fancier things, for example
converting (+ x (+ 1 x) 1 x) to (+ (* 3 x) 2).
Suggestion: look at some of the output produced by diff and try
to identify simple, high-impact transformations that make a big difference
in the readability of the output. Turn in a copy of your Scheme source file using the regular online collection
dropbox. Please put all of your functions in one file named hw3.scm.
If you attempted extra credit please turn in two versions of your program,
the first one named hw3.scm without extra credit, and a second
one named hw3-extra.scm with
extra credit.
Be sure that your name is included at the beginning of the filein a comment.