## **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

## 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.