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

From Drewiki
Jump to: navigation, search

Problem

Suppose we want to modify the differentiation program so that it works with ordinary mathematical notation, in which + and * are infix rather than prefix operators. Since the differentiation program is defined in terms of abstract data, we can modify it to work with different representations of expressions solely by changing the predicates, selectors and constructors that define the representation of the algebraic expressions on which the differentiator is to operate.

a. Show how to do this in order to differentiate algebraic expressions presented in infix form, such as (x + (3 * (x + (y + 2)))). To simplify the task, assume that + and * always take two arguments and that expressions are fully parenthesized.

b. The problem becomes substantially harder if we allow standard algebraic notation, such as (x + 3 * (x + y + 2)), which drops unnecessary parentheses and assumes that multiplication is done before addition. Can you design appropriate predicates, selectors and constructors for this notation such that our derivative program still works?

Solution, part a.

Let's handle + first. Here's our original program from exercise 2.56, which handles exponentiation, as well:

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

To switch from prefix notation to infix, only the positions of the operator and addend are swapped; the augend remains the same. We simply need to change sum?, addend and make-sum:

(define (sum? x) 
  (and (pair? x) (eq? (cadr x) '+))) 
 
(define (addend s) (car s)) 
 
(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))))

The changes needed for multiplication and (while we're at it) are exponentiation analogous:

(define (product? x) 
  (and (pair? x) (eq? (cadr x) '*))) 
 
(define (multiplier p) (car p)) 
 
(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? (cadr x) '**)))
 
(define (base e) (car e))
 
(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:

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

Output:

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

Output:

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

Output:

(4 * (x ** 3))

Perfect!

Solution, part b.

Left as as exercise for the reader, for now ;)

Personal tools