SICP 全笔记

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?

带括号的中序表达式

将表达式改为中序表达式只需要像下面这样修改 constructor 和 selector 即可。

(load "differentiation.scm")

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

(define (addend s) (car s))

(define (augend s) (caddr s))

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

(define (multiplier p) (car p))

(define (multiplicand p) (caddr p))

;;; tests begin
(load "../testframe.scm")

;; regression tests
(assert= (deriv '(x + 3) 'x) 1)

(asserteq? (deriv '(x * y) 'x) 'y)

(assertequal? (deriv '((x * y) * (x + 3)) 'x)
              '((x * y) + (y * (x + 3))))

去掉括号的中序表达式

去掉了括号之后对于 + 号而言影响不大，augend 和 addend 这样的 selector 不会受优先级的影响。

但乘法影响很大。比如

(3 * 5 + 2)
(3 * 5 * 2)

这样的表达式对于乘号来说，multiplicand 过程无法判断 5 之后是否还是乘数的一部分，所以无法做出选择。在不修改 deriv 的前提下，是没有办法去设计另外一套系统使其工作的。