4
\$\begingroup\$

Exercise 2.57. Extend the differentiation program to handle sums and products of arbitrary numbers of (two or more) terms. Then the last example above 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.

I wrote the following solution.

(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 (exponent exp)
                       (make-exponentiation (base exp) (- (exponent exp) 1))))
        (else
         (error "unknown expression type -- DERIV" exp))))

(define (variable? x) (symbol? x))

(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))

(define (make-sum . a)
  (define (iter sum rest) 
    (cond ((null? rest) (if (zero? sum) '() (list sum)))
          ((=number? (car rest) 0) (iter sum (cdr rest)))
          ((number? (car rest)) (iter (+ sum (car rest)) (cdr rest)))
          (else (cons (car rest) (iter sum (cdr rest))))))
  (let ((result (iter 0 a)))
    (if (= (length result) 1)
        (car result)
        (cons '+ result))))

(define (=number? exp num)
  (and (number? exp) (= exp num)))

(define (make-product . a)
  (define (iter product rest)
    (cond ((null? rest) (if (= 1 product) '() (list product)))
          ((=number? (car rest) 1) (iter product 
                                         (cdr rest)))
          ((number? (car rest)) (iter (* product (car rest)) 
                                      (cdr rest)))
          (else 
           (let ((result (iter product (cdr rest))))
             (if (and (pair? result) (eq? (car result) 0))
                 (list 0)
                 (cons (car rest) result))))))
  (let ((result (iter 1 a)))
    (if (= (length result) 1)
        (car result)
        (cons '* result))))

(define (sum? x)
  (and (pair? x) (eq? (car x) '+)))

(define (addend s) (cadr s))

(define (augend s) (if (> (length s) 3)
                       (cons '+ (cddr s))
                       (caddr s)))

(define (product? x)
  (and (pair? x) (eq? (car x) '*)))

(define (multiplier p) (cadr p))

(define (multiplicand p) (if (> (length p) 3) 
                             (cons '* (cddr p))
                             (caddr p)))

(define (exponentiation? x)
  (and (pair? x) (eq? (car x) '**)))
(define (base s) (cadr s))
(define (exponent s) (caddr s))
(define (make-exponentiation m1 m2)
  (cond ((=number? m2 0) 1)
        ((= m2 1) m1)
        (else (list '** m1 m2))))

Can it be improved? In particular, look closely at make-product and make-sum.

\$\endgroup\$
4
\$\begingroup\$

Your have the right ideas for implementing make-sum and make-product. You may improve upon them in the following ways, in my opinion.

Within the two functions, you employ an inner function iter to partition numeric and non-numeric terms. Traditionally, one uses the name iter to represent an iterative function; your definition, however, is most certainly recursive. To make it truly iterative, one may use two accumulators--one for the sum of all numeric terms and the other for the rest of the terms. Then one may return the cons of the two accumulators when the iteration terminates.

One may allow make-sum (and similarly make-product) to handle other sum-type objects in its terms list as well--simply test with sum?, then append its terms.

Finally, there are several cases that must be handled when iteration terminates: rest may be empty or it may contain one or more items; sum-numbers may be zero or non-zero.

Here's an implementation (naming scheme is slightly different from yours--in the iter function, terms is the list of remaining terms to be iterated upon, sum-numbers is the sum of all numeric terms seen so far, rest is a list of all non-numeric terms seen so far):

(define (make-sum . terms)
  (define (iter terms sum-numbers rest)
    (cond
      ((null? terms) (cons sum-numbers rest))
      ((=number? (car terms) 0) (iter (cdr terms) sum-numbers rest))
      ((number? (car terms)) (iter (cdr terms) (+ sum-numbers (car terms)) rest))
      ((sum? (car terms)) (iter (append (cdar terms) (cdr terms)) sum-numbers rest))
      (else (iter (cdr terms) sum-numbers (cons (car terms) rest)))))
  (let*
      ((result (iter terms 0 null))
       (sum-numbers (car result))
       (rest (cdr result)))
    (if (null? rest)
        sum-numbers
        (if (zero? sum-numbers)
            (if (null? (cdr rest))
                (car rest)
                (cons '+ rest))
            (cons '+ (cons sum-numbers rest))))))

(define (make-product . terms)
  (define (iter terms sum-numbers rest)
    (cond
      ((null? terms) (cons sum-numbers rest))
      ((=number? (car terms) 0) (cons 0 null))
      ((=number? (car terms) 1) (iter (cdr terms) sum-numbers rest))
      ((number? (car terms)) (iter (cdr terms) (* sum-numbers (car terms)) rest))
      ((product? (car terms)) (iter (append (cdar terms) (cdr terms)) sum-numbers rest))
      (else (iter (cdr terms) sum-numbers (cons (car terms) rest)))))
  (let*
      ((result (iter terms 1 null))
       (sum-numbers (car result))
       (rest (cdr result)))
    (if (null? rest)
        sum-numbers
        (if (zero? sum-numbers)
            (if (null? (cdr rest))
                (car rest)
                (cons '* rest))
            (cons '* (cons sum-numbers rest))))))

One may also simplify the definitions of augend and multiplicand by using make-sum and make-product respectively:

(define (augend s) (apply make-sum (cddr s)))

(define (multiplicand p) (apply make-product (cddr p)))

Note the similarities between make-sum and make-product. It may be possible to factor out some code. One may also use library functions such as partition (if available) to simplify the code.

\$\endgroup\$
  • \$\begingroup\$ I see what you mean about (augend ) and (multiplicand ) as well as the iter/rec naming. Could you elaborate a bit on why it is better to add the additional (product? ) or (sum? ) test? I think I understand, but I'm curious what you think. \$\endgroup\$ – jaresty Apr 25 '11 at 0:57
  • \$\begingroup\$ @jaresty: By handling a sum-type object in make-sum, the following simplification becomes possible: (make-sum 2 '(+ 5 x)) => '(+ 7 x) \$\endgroup\$ – Adeel Zafar Soomro Apr 25 '11 at 12:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.