CSE 413 21sp Assignment 3 - Racket Programming

Tuesday, April 20, by 11 p.m. You should use Gradescope to submit your assignment. Details are given in the "What to hand in" section at the bottom of the assignment.

Overview

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) (x^r) = r * (x)^r-1                                         Power rule

More Complex Rules

(d/dx) (e^x) = e^x

(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) (e^f(x)) = e^f(x) * (d/dx)(f(x))                Applying the chain rule.

Requirements

Your program only needs to 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 x^y where y is an integer (expt x y). You can add additional operators, or, for example generalize x^y to handle the case where y is a variable other than x, 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 using Racket's standard prefix notation. That is,

Formula	List Representation
`4`	`4`
`2x + 4`	`(+ (* 2 x) 4)`
`x + (x * x)`	`(+ x (* x x))`
`3x + 4y + 6x³`	`(+ (* 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))		=> (+ (* 2 1) (* 0 x)) 	       (i.e. 2)

> (diff 'y '(* 2 x))		=> (+ (* 2 0) (* 0 x)) 	       (i.e. 0)

> (diff 'x '(+ x (* x x)))	=> (+ 1 (+ (* x 1) (* 1 x)))   (i.e. 1 + x + x)

> (diff 'x '(expt x 4))		=> (* 4 (expt x 3))            (i.e. 4 * x³)

Implementation

Your function (diff v E) should 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 in your source file before your dispatch table 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 look up 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 main diff function should handle differentiation of numbers and symbols (single variables such as x or y) directly. For operators, it should look up and apply 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

You should include the dispatch table code above in your program exactly as shown (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))

When you include appropriate constructor and access functions, the code that differentiates expressions can be written in terms of expression arguments and operators, not car, cdr, cadar, and similar things. Using appropriate functions should make the code 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) implement and run 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 (all-defined-out))

at the beginning of your hw3.rkt file to make all of the functions defined in it visible to the file containing the tests (as well as to the grading infrastructure code). This version of provide makes all of the functions in hw3.rkt visible to other files. If we were working on a larger set of code, we probably would use a more restricted version of provide listing only the functions we wish to make visible, like (provide diff). For this assignment it's probably easier just to export everything. If that does create some sort of global name conflicts, feel free to fall back on selectively exporting only needed functions.

After adding provide to the hw3.rkt file, create a file hw3-tests.rkt to hold the tests (you must 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")

Feel free to add additional tests for other functions in your code, but be sure to have a broad range of tests for diff itself. 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 should not include this much verbiage in the tests you turn in.

One caution: in the past, we discovered that it is not always sufficient to have the right tests and functions in the files. After you edit these files, it may be 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. Don't worry about this unless you observe the problem.

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 wish be sure to label those extra credit options and submit the extended version of the program using the file name hw3-extra.rkt. You should create additional tests for your extensions and submit those in a file named hw3-extra-tests.rkt. Be sure to include comments at the top of your hw3-extra.rkt file briefly summarizing your extra extensions.

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). (Note that since the + function accepts an arbitrary number of operands, it works just fine with a single operand.) 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. The exact number and kinds of transformations to include is up to you.
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 if you have lots of tests) 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

Use Gradescope to submit your hw3.rkt and hw3-tests.rkt files. If you attempted any extra credit please turn in two versions of your program, the first in the original files without extra credit, and the second in another 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. There will be two separate assignments in Gradescope: Homework 3 and Homework 3 Extra. You should turn in the required part of the assignment as Homework 3. If you do any extra credit work, you should turn in those files using the Homework 3 Extra Gradescope assignment, but also be sure to turn in the basic assignment as Homework 3. If you do not do any of the extra credit parts, you do not need to turn in anything for Homework 3 Extra.

Be sure that your name is included at the beginning of each file in a comment.