2011-11-05

SICP Exercise 2.56: Differentiating Exponentials

Show how to extend the basic differentiator to handle more kinds of expressions. For instance, implement the differentiation rule
d(un) = nxn-1 du
 dx          dx
by adding a new clause to the deriv program and defining appropriate procedures exponentiation?, base, exponent, and make-exponentiation. (You may use the symbol ** to denote exponentiation.) Build in the rules that anything raised to the power 0 is 1 and anything raised to the power 1 is the thing itself.

Let's start with the procedures... And in fact let's do them in the reverse order in which they're listed above, and start with make-exponentiation. Like the implementations of make-sum and make-product we want to build in some rules that reduce the expression to its simplest form. For exponents we can define the following reductions:
  • 1 raised to the power of anything is 1.
  • Anything raised to the power of 0 is 1.
  • Anything raised to the power of 1 is itself.
  • If both the base and the exponent are numbers then make-exponentiation can calculate and return the exponent.
In any other case we simply build up the appropriate list representation and return that. This gives us the following implementation:
(define (make-exponentiation base exponent)
  (cond ((=number? base 1) 1)
        ((=number? exponent 0) 1)
        ((=number? exponent 1) base)
        ((and (number? base) (number? exponent)) (expt base exponent))
        (else (list '** base exponent))))
Let's check this works:
> (make-exponentiation 1 24)
1
> (make-exponentiation 2 4)
16
> (make-exponentiation 'a 3)
(** a 3)
> (make-exponentiation 5 'b)
(** 5 b)
> (make-exponentiation 'a 'b)
(** a b)
> (make-exponentiation 'a 1)
a
> (make-exponentiation 'a 0)
1
> (make-exponentiation 4 1)
4
> (make-exponentiation 4 0)
1
The selectors and predicates then just follow the same pattern as the equivalents for sums and products:
(define (base x) (cadr x))
(define (exponent x) (caddr x))
(define (exponentiation? x)
  (and (pair? x) (eq? (car x) '**)))
And again, a quick test:
> (base (make-exponentiation 'a 'b))
a
> (exponent (make-exponentiation 'a 'b))
b
> (exponentiation? (make-exponentiation 'a 'b))
#t
> (exponentiation? (make-product 'a 'b))
#f
All we need to do now is to extend deriv, adding a clause that uses exponentiation? to test whether or not the expression is an exponentiation and, if it is, applies the differentiation rule:
(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
           (make-product (multiplier exp)
                         (deriv (multiplicand exp) var))
           (make-product (deriv (multiplier exp) var)
                         (multiplicand exp))))
        ((exponentiation? exp)
         (make-product
           (make-product (exponent exp)
                         (make-exponentiation (base exp)
                                              (make-sum (exponent exp) -1)))
           (deriv (base exp) var)))
        (else
         (error "unknown expression type -- DERIV" exp))))
Let's give this a spin:
> (deriv (make-exponentiation 'a 5) 'a)
(* 5 (** a 4))
> (deriv (make-exponentiation 'a 'b) 'a)
(* b (** a (+ b -1)))
> (deriv (make-exponentiation 'a (make-sum 'a 'b)) 'a)
(* (+ a b) (** a (+ (+ a b) -1)))

No comments:

Post a Comment