#lang racket ;;; CSE 341 - Racket ;;; A classic example of Scheme/Racket programs as data: symbolic differentiation. Adapted from ;;; "Structure and Interpretation of Computer Programs" Chapter 2. Somewhat modified: doesn't use ;;; constructor functions, and it separates out finding the derivative from simplifying expressions. ;;; Includes unit tests. ;; the top-level function deriv takes an expression and a variable, ;; and returns the derivative of that expression with respect to the variable, ;; in simplified form (define (deriv exp var) (simplify (basic-deriv exp var))) ;; basic-deriv takes the derivative of an expression exp with respect to a variable and ;; return the result without simplification (define (basic-deriv exp var) (cond ((number? exp) 0) ((symbol? exp) (if (eq? exp var) 1 0)) ((sum? exp) (list '+ (basic-deriv (left exp) var) (basic-deriv (right exp) var))) ((product? exp) (list '+ (list '* (left exp) (basic-deriv (right exp) var)) (list '* (basic-deriv (left exp) var) (right exp)))) (else (error "unknown expression type -- basic-deriv" exp)))) ;; predicates and access functions ;; test whether a list structure is a sum (define (sum? x) (and (pair? x) (eq? (car x) '+))) ;; test whether a list structure is a product (define (product? x) (and (pair? x) (eq? (car x) '*))) ;; get the left hand part of a sum or product (define (left exp) (cadr exp)) ;; get the right hand part of a sum or product (define (right exp) (caddr exp)) ;; basic simplification function (nothing too fancy ... doesn't know about commutativity or associativity) (define (simplify exp) (cond ((sum? exp) (simplify-sum exp)) ((product? exp) (simplify-product exp)) ;; if we get here, we can't simplify exp (else exp))) (define (simplify-sum exp) ;; to simplify a sum, we need to first recursively simplify the left and right parts (let ((a (simplify (left exp))) (b (simplify (right exp)))) (cond ((equal? 0 a) b) ((equal? 0 b) a) ((and (number? a) (number? b)) (+ a b)) (else (list '+ a b))))) (define (simplify-product exp) (let ((a (simplify (left exp))) (b (simplify (right exp)))) (cond ((or (equal? 0 a) (equal? 0 b)) 0) ((equal? 1 a) b) ((equal? 1 b) a) ((and (number? a) (number? b)) (* a b)) (else (list '* a b))))) ;; Unit tests. See ;; http://docs.racket-lang.org/rackunit/quick-start.html ;; for documentation on Racket's unit testing library. (require rackunit) (define deriv-tests (test-suite "tests for deriv program" (check-equal? (deriv 'x 'x) 1 "deriv of x wrt x") (check-equal? (deriv 'y 'x) 0 "deriv of y wrt x") (check-equal? (deriv '(+ x 3) 'x) 1 "deriv of (+ x 3) wrt x") (check-equal? (deriv '(* (+ 2 3) x) 'x) 5 "deriv of unsimplified expression") (check-equal? (deriv '(+ x y) 'x) 1 "deriv of (+ x y) wrt x") ;; simplification is not as clever as it could be in the following case: (check-equal? (deriv '(* (+ x 1) (+ x -1)) 'x) '(+ (+ x 1) (+ x -1)) "deriv of (* (+ x 1) (+ x -1)) wrt x") (check-equal? (deriv '(* (* x y) (+ x 3)) 'x) '(+ (* x y) (* y (+ x 3))) "complex deriv") )) (require rackunit/text-ui) ;; this line runs the tests .... (run-tests deriv-tests)