2.58

练习 2.58 假定我们希望修改求导程序，使它能用于常规数学公式，其中+和*采用的是中缀运算符而不是前缀。由于求导程序是基于抽象数据定义的，要修改它，使之能用于另一种不同的表达式表示，我们只需要换一套工作在新的、求导程序需要使用的代数表达式的表示形式上的谓词、选择函数和构造函数。

a）请说明怎样做出这些过程，以便完成在中缀表示形式（例如(x+(3(x+(y+2))))）上的代数表达式求导。为了简化有关的工作，现在可以假定+和总是取两个参数，而且表达式中已经加上了所有的括号。

b）如果允许标准的代数写法，例如(x+3*(x+y+2))，问题就会变得更困难许多。在这种表达式里可能不写不必要的括号，并要假定乘法应该在加法之前完成。你还能为这种表示方式设计好适当的谓词、选择函数和构造函数，使我们的求导程序仍然能工作吗？

a）似乎只需要修改 make-sum、addend、augend、make-product、multiplier、multiplicant、以及相应的判断过程 product? 和 sum?。

先复用一点上一练习的代码：

(define (=number? v n)
    (if (number? v)
        (= v n)
        #f
    )
)

(define (error msg v)
    (list msg v)
)

(define variable? symbol?)
(define (same-variable? v1 v2)
    (and (variable? v1) (variable? v2) (eq? v1 v2))
)
(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
        ((=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 car)
(define augend caddr)
(define (product? x) (and (pair? x) (eq? (cadr x) '*)))
(define multiplier cadr)
(define multiplicand caddr)

(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)
                )
            )
        )
        (else
            (error "unknown expression type -- DERIV" exp)
        )
    )
)

; 期待返回 1
(deriv '(x + 3) 'x)

定义 exponentiation?：

(define (exponentiation? exp)
    (and (pair? exp) (eq? (car exp) '**))
)

; 期待返回 true
(exponentiation? '(** x 3))

定义 base：

(define base cadr)

; 期待返回 x
(base '(** x 3))

定义 exponent：

(define exponent caddr)

; 期待返回 3
(exponent '(** x 3))

定义 make-exponentiation：

(define (make-exponentiation m1 m2) (list '** m1 m2))

; 期待返回 (** x 3)
(make-exponentiation 'x 3)

增加一个子句后的 deriv：

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

(deriv '(** x 0) 'x)

; 期待得到 3x^2 的结果
(deriv '(** x 3) 'x)

现在尝试直接计算：

$$(x+(3*(x+(y+2))))$$

; 期待得到 4
(deriv '(x + (3 * (x + (y + 2)))) 'x)

可以看到，正确得到了结果。但没有化简。

现在修改一下和的表示：

(define (augend exp)
    (if (<= (length (cddr exp)) 1)
        (caddr exp)
        (cddr exp)
    )
)

(define (make-sum addend augend)
    (cond 
        ((=number? addend 0)
             (if (pair? augend)
                (make-sum (car augend) (cdr augend))
                augend
             )
        )
        (
            (or (=number? augend 0) (null? augend)) 
            addend
        )
        ((and (number? addend) (number? augend)) (+ addend augend))
        (
            (and (number? addend) (pair? augend) (number? (car augend)))
            (make-sum (+ addend (car augend)) (cdr augend))
        )
        (else
            (list '+ addend augend)
        )
    )
)

(make-sum 1 (list 2 3 4 5 6))

(augend '(+ 2 3 4 5 6))

再来修改一下乘积的表示：

(define (make-product m1 m2) 
    (cond
        ((null? m2) m1)
        ((=number? m1 0) 0)
        ((=number? m1 1)
            (if (pair? m2)
                (make-product (cadr m2) (cddr m2))
                m2
            ) 
        )
        ((=number? m2 0) 0)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        (
            (and (number? m1) (pair? m2) (number? (car m2)))
            (make-product (* m1 (car m2)) (cdr m2))
        ) 
        (else 
            (if (pair? m2)
                (list '* m1 (make-product (car m2) (cdr m2)))            
                (list '* m1 m2)
            )
        )
    )
)

(define (multiplicand exp) 
    (if (<= (length (cddr exp)) 1)
        (caddr exp)
        (cons '* (cddr exp))
    )
)

(multiplicand '(* 1 2 3 4 5))

(multiplicand '(* 1 2))

(make-product 1 (list 2 3 4 5 6))

(make-sum 'x 3)

(make-product 'x (list 'y (make-sum 'x 3)))

再来计算一次：

; 期待得到 4
(deriv '(x + (3 * (x + (y + 2)))) 'x)

b) 如果去掉括号还要求正确工作，就更有挑战性了。不过对于这个具体的例子，居然现在的版本就能计算正确了：

; 期待得到 4
(deriv '(x + 3 * (x + y + 2)) 'x)

再细想了一下，其实没有那么难。只要在求导程序里，优先对低优先级的运算做判断和处理就行了。这也是为什么现在的程序就能正确计算的原因，因为现在的实现，的确是先判断和处理加法，然后是乘法，最后是幂运算。

受此启发，将求导运算集成进了“极客计算器”中，可以点击链接体验。