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

## Problem

Show how to extend the basic differentiator to handle more kinds of expressions. For instance, implement the differentiation rule

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.

## Discussion

Here are the relevant definitions given in the text that we'll need for this exercise. The particular version of `fast-expt` given here comes from SICP exercise 1.16.

(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 (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))))

## Solution

The definitions of `exponentiation?`, `base` and `exponent` are analogous to `sum?`, `addend` and `augend`, respectively.

(define (exponentiation? x) (and (pair? x) (eq? (car x) '**))) (define (base e) (cadr e)) (define (exponent e) (caddr e))

Test these definitions:

(exponentiation? '(** a b))

*Output:*

`
`

#t

(exponentiation? '(* a b))

*Output:*

`
`

#f

(base '(** a b))

*Output:*

`
`

a

(exponent '(** a b))

*Output:*

`
`

b

The definition of `make-exponentiation` is analogous to `make-sum`.

In addition to the simplification rules demanded by the exercise, we'll also simplify the case where 1 to any power is 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))))

Test `make-exponentiation`:

(make-exponentiation 'a 'b)

*Output:*

`
`

(** a b)

(make-exponentiation 'a 1)

*Output:*

`
`

a

(make-exponentiation 'a 0)

*Output:*

`
`

1

(make-exponentiation 2 16)

*Output:*

`
`

65536

(make-exponentiation 2 'b)

*Output:*

`
`

(** 2 b)

(make-exponentiation 'a 3)

*Output:*

`
`

(** a 3)

(make-exponentiation 1 'b)

*Output:*

`
`

1

Adding an exponentiation case to the definition of `deriv` given in the text is fairly straightforward using the differentiation rule shown above:

(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))))

Tests:

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

*Output:*

`
`

0

(deriv '(** x 3) 'x)

*Output:*

`
`

(* 3 (** x 2))

(deriv '(** x y) 'x)

*Output:*

`
`

(* y (** x (+ y -1)))

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

*Output:*

`
`

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

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

*Output:*

`
`

(* (* (* 4 x) (** (* 2 (** x 2)) (+ (* 4 x) -1))) (* 2 (* 2 x)))

As the last test shows, the algebraic simplification of our system leaves something to be desired.