my attempt to do the exercises in sicp.

Monday, July 21, 2008

sicp exercise 2.58 a.

;; Exercise 2.58.  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?

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

(define (sum? exp) (and (pair? exp) (eq? '+ (cadr exp))))
(define (addend exp) (car exp))
(define (augend exp) (caddr exp))

(define (product? exp) (and (pair? exp) (eq? '* (cadr exp))))
(define (multiplicand exp) (car exp))
(define (multiplier exp) (caddr exp))

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

(define (make-sum x y)
  (cond ((and (number? x) (= x 0)) y)
        ((and (number? y) (= y 0)) x)
        ((and (number? x) (number? y)) (+ x y))
        (else (list x '+ y))))

(define (make-product x y)
  (cond ((and (number? x) (= x 1)) y)
        ((and (number? y) (= y 1)) x)
        ((and (number? x) (= x 0)) 0)
        ((and (number? y) (= y 0)) 0)
        ((and (number? x) (number? y)) (* x y))
        (else (list x '* y))))

(define (make-exponentiation base exponent)
  (cond ((and (number? exponent) (= exponent 0)) 1)
        ((and (number? exponent) (= exponent 1)) base)
        (else (list base '** exponent))))

(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-product (multiplicand exp)
                                  (deriv (multiplier exp) var))
                    (make-product (multiplier exp)
                                  (deriv (multiplicand exp) var))))
        ((exponentiation? exp)
               (make-product (exponent exp)
                             (make-exponentiation (base exp) (- (exponent exp) 1))
                             (deriv (base exp) var))))
        (else (error "ERROR-" exp))))

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

No comments: