![university of washington logo](/images/purple_w.png)
CSE 413 14au Assignment 3 - Racket Programming
Due: Online via the Catalyst Dropbox by 11 pm, Thursday, Oct. 16, 2014.
For this project you will write a racket program to differentiate simple expressions. In case calculus is a distant memory, the rules for differentiation go something like this:
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 individual variable value,
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 source file so they will be defined
when diff-dispatch
is initialized. 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 need to 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.
The code for your program should be stored in a file named hw3.rkt
.
Racket 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 racket 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 car
, cdr
, cadar
, and similar things,
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 use map
if appropriate to implement 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. 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) package the tests using Racket's RackUnit testing framework.
Look at the Quick Start Guide in the RackUnit documentation for an overview of how unit testing works in Racket. Briefly, you need to include
(provide diff)at the beginning of your
hw5.rkt
file to make the diff
function visible to the file containing the tests.
Then create a file hw5-tests.rkt
to hold the tests (you should use this file name). At the top of the test file, include these lines:
(require rackunit) (require "hw3.rkt")The remainder of the
hw3-tests.rkt
file should contain
tests for your diff
function. The simplest versions of
the RackUnit test functions check that execution of a function
produces an expected value:
(check-equal? test-expression expected-value "string identifying test")
If you have larger collections of tests or need more elaborate setup functions, you can create test suites. See the RackUnit Quick Start documentation for details.
We have provided two files to give you an idea of how the testing
framework is
structured. hw3demo.rkt
contains a list append function like the ones we've written in class.
File hw3demo-tests.rkt
contains a couple of basic tests for this function. Load both files
into DrRacket and click Run in the test file window to run the
tests. Notes: You may need to use Run in the definitions file first to
be sure DrRacket has analyzed the file being tested. The demo tests
file contains lots of comments meant to explain the contents of the
file. You do not need to include this much verbiage in the tests you
turn in.
One caution: while preparing this assignment we discovered that it is not always sufficient to put the right tests and functions in the files. It is necessary to save the files to disk first, otherwise the testing framework might not be able to find the latest versions of the files and you will get an error message that it cannot find the functions.
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 and tests in files named hw3.rkt
and hw3-tests.rkt
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.rkt
.
You should create additional tests for your extensions and submit those in a file named hw3-extra-tests.rkt
.
- Simplify the output: If you simply run
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))
should produce the simplified expression. 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, for instance converting:(* 1 (+ x 0) x)
to(* (+ x) x)
. 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 bydiff
and try to identify simple, high-impact transformations that make a big difference in the readability of the output. - Add more functions: Add in trig functions:
cos, sin, tan, or other functions: exp, log, sqrt, quotients, or whatever
you want that expands the
capabilities of your
diff
function. See the racket reference pages for a list of functions found in racket, or invent notation for functions of your own (but be sure to clearly document your extensions if you invent new notation).
- (simple, but useful) Organize the tests in test suites: Organize your tests into suites, one or more for the basic requirements, and one or more for each major extension.
What to Hand In
Electronic Submission
Turn in a copy of your hw3.rkt
and hw3-tests.rkt
files using the regular online collection
dropbox.
If you attempted extra credit please turn in two versions of your program,
the first in the original files without extra credit, and the second
pair of files named
hw3-extra.rkt
and hw3-extra-tests.rkt
with the
extra credit version of the program and the additional tests for the extra credit part..
Be sure that your name is included at the beginning of each file in a comment.
Computer Science & Engineering University of Washington Box 352350 Seattle, WA 98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX