Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

SICP exercise 2.57

From Drewiki
Jump to: navigation, search

Problem

Extend the differentiation program from SICP exercise 2.56 to handle sums and products of arbitrary numbers of (two or more) terms. Then the example in exercise 2.56 could be expressed as

(deriv '(* x y (+ x 3)) 'x)

Try to do this by changing only the representation for sums and products, without changing the deriv procedure at all. For example, the addend of a sum would be the first term, and the augend would be the sum of the rest of the terms.

Dependencies

Here are the definitions we'll start with from previous exercises:

(define (variable? x) (symbol? x)) 
 
(define (same-variable? v1 v2) 
  (and (variable? v1) (variable? v2) (eq? v1 v2))) 
 
(define (sum? x) 
  (and (pair? x) (eq? (car x) '+))) 
 
(define (addend s) (cadr s)) 
 
(define (augend s) (caddr s)) 
 
(define (product? x) 
  (and (pair? x) (eq? (car x) '*))) 
 
(define (multiplier p) (cadr p)) 
 
(define (multiplicand p) (caddr p)) 
 
(define (=number? exp num) 
  (and (number? exp) (= exp num))) 
 
(define (make-sum a1 a2) 
  (cond ((=number? a1 0) a2) 
        ((=number? a2 0) a1) 
        ((and (number? a1) (number? a2)) (+ a1 a2)) 
        (else (list '+ a1 a2)))) 
 
(define (make-product m1 m2) 
  (cond ((or (=number? m1 0) (=number? m2 0)) 0) 
        ((=number? m1 1) m2) 
        ((=number? m2 1) m1) 
        ((and (number? m1) (number? m2)) (* m1 m2)) 
        (else (list '* m1 m2)))) 
 
(define (exponentiation? x)
  (and (pair? x) (eq? (car x) '**)))
 
(define (base e) (cadr e))
 
(define (exponent e) (caddr e))
 
(define (square x) (* x x))
 
(define (even? n)
  (= (remainder n 2) 0))
 
(define (fast-expt b n)
  (define (fast-expt-iter b n a)
    (cond ((= n 0) a)
          ((even? n) (fast-expt-iter (square b) (/ n 2) a))
          (else (fast-expt-iter b (- n 1) (* a b)))))
  (fast-expt-iter b n 1))
 
(define (make-exponentiation b e)
  (cond ((=number? e 0) 1)
        ((=number? e 1) b)
        ((=number? b 1) 1)
        ((and (number? b) (number? e)) (fast-expt b e))
        (else (list '** b e))))
 
(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)
         (let ((u (base exp))
               (n (exponent exp)))
           (make-product
            (make-product n
                          (make-exponentiation u
                                               (make-sum n -1)))
            (deriv u var))))
        (else
         (error "unknown expression type -- DERIV" exp))))

Solution

Let's implement multi-term sums first. The first thing we need to do is to determine how the current implementations of addend and augend behave when given multi-term sums. Here's a test case:

(addend '(+ 3 4 5))

Output:

3


addend works fine; what about augend?

(augend '(+ 3 4 5))

Output:

4


augend returns only the second term. We want it to return the sum of the remaining terms... but does that mean it should evaluate the sum of the remaining terms, or simply produce a new expression to be evaluated by another procedure? In other words, should (augend '(+ 3 4 5)) return 9, or should it return the list (+ 4 5)?

If we want augend to return the value 9, it'll need to evaluate the expression (+ 4 5). augend can't currently do that, but make-sum can; so we could redefine augend to call make-sum on the remaining terms. However, what about a sum with more than 3 terms, e.g., (augend '(+ 3 4 5 6))? make-sum takes only 2 arguments, but the exercise asks us to handle sums of arbitrary length, so if we were to redefine augend to call make-sum, we'd either need to change make-sum to take a list of terms, or we'd need to add code to augend so that it iteratively calls make-sum to reduce the multi-term sum by pairs of terms. That sounds rather complicated, so let's avoid it if possible. Redefining make-sum to take a list of terms might be more elegant, but the exercise asks us to try to avoid changing deriv, and deriv calls make-sum, so we should also avoid that strategy if we want to complete the exercise in the manner intended by Abelson and Sussman.

That leads us back to the alternative definition of augend, the one that simply produces a new expression instead of evaluating one. That is, after all, what the original definition does when we apply it to a two-term sum such as (+ 4 (+ a b)): it returns the list (+ a b), since that's the second term of the sum. Therefore, if the new definition is such that (augend '(+ 4 a b)) returns the list (+ a b), that's very much in keeping with the original definition. Note that this behavior is compatible with the existing definition of deriv: when deriv computes the derivative of a multi-term sum expression, it evaluates the expression (deriv (augend exp) var), and the (augend exp) sub-expression will return another sum expression, eliding the first term of the original expression exp. This sub-expression will in turn be evaluated recursively by deriv, and so on. No changes are required to make-sum, either, because deriv still applies it to just two arguments, namely the derivatives of (addend exp) and (augend exp).

This looks like a promising design path, so let's try it. Before we handle sums with more than 2 terms, however, we must ensure we can still handle sums with just 2 terms. Evaluating the expression (augend '(+ a b)) should return the value b, not the nonsensical expression (+ b). Therefore, we'll need to determine whether an expression has more than 2 terms. An expression with exactly two terms is called a binary expression. If we assume that all expressions are well-formed and have at least 2 terms, we can identify a binary expression with the following procedure:

(define (binary-expression? e)
  (null? (cdddr e)))

Let's test it:

(binary-expression? '(+ a b))

Output:

#t
(binary-expression? '(+ a b c))

Output:

#f


Then we can define the multi-term-capable version of augend simply as

(define (augend s)
  (if (binary-expression? s)
      (second-term s)
      (cons '+ (all-but-first-term s))))

where the helper procedures second-term and all-but-first-term are just nice wrappers around the appropriate primitive list procedures:

(define (second-term e)
  (caddr e))
 
(define (all-but-first-term e)
  (cddr e))

Note that all-but-first-term returns a list of terms, which is why we cons a + symbol onto it to create the new sum expression in augend.

Let's test each of these helper procedures individually, and then test the new definition of augend:

(second-term '(+ a b))

Output:

b
(all-but-first-term '(+ a b c d))

Output:

(b c d)
(augend '(+ a b))

Output:

b
(augend '(+ a b c d)

Output:

(+ b c d)


That looks good. Now let's quickly move on to multi-term products. Obviously, we can handle them exactly the same way as multi-term sums, except that we need to cons a * symbol onto the list of remaining terms when returning a multi-term multiplicand. We can re-use the definitions of binary-expression?, second-term and all-but-first-term since they're independent of the operator used in the expression. All we need is the new definition of multiplicand:

(define (multiplicand p)
  (if (binary-expression? p)
      (second-term p)
      (cons '* (all-but-first-term p))))

In fact, because multiplicand looks nearly identical to the definition of augend, we could factor almost all of the code out of these two procedures into a generic procedure. It's a bit difficult to come up with a good name for that procedure, but we might call it reduce-expression. Let's do that now:

(define (reduce-expression e op)
  (if (binary-expression? e)
      (second-term e)
      (cons op (all-but-first-term e))))
 
(define (augend s) (reduce-expression s '+))
 
(define (multiplicand p) (reduce-expression p '*))

Now test:

(augend '(+ a b))

Output:

b
(augend '(+ a b c d))

Output:

(+ b c d)
(multiplicand '(* a b))

Output:

b
(multiplicand '(* a (+ b c)))

Output:

(+ b c)
(multiplicand '(* a b c d))

Output:

(* b c d)

That looks perfect. Now let's try to differentiate some expressions with multi-term sums and products. First, here's the example given in the text:

(deriv '(* x y (+ x 3)) 'x)

Output:

(+ (* x y) (* y (+ x 3)))

That's exactly the answer we got before when we evaluated the equivalent original input expression (with binary-only terms) (* (* x y) (+ x 3)) 'x), so we know our new system is working. And, of course, that original expression should also work:

(deriv '(* (* x y) (+ x 3)) 'x)

Output:

(+ (* x y) (* y (+ x 3)))

Yep, it works, too.

Here's another example:

(deriv '(+ x 3 4 (* 2 x 3)) 'x)

Output:

7

And 7 is, in fact, the right answer.

Note that this new multi-term program is just a small perturbation of the original program (just 4 short new procedures and 2 redefined ones), demonstrating the flexibility of good data abstractions.

Personal tools