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)
​x
 
1

定义 exponentiation?：

 
(define (exponentiation? exp)
  (and (pair? exp) (eq? (car exp) '**))
  )
​
; 期待返回 true
(exponentiation? '(** x 3))
 
true

定义 base：

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

定义 exponent：

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

定义 make-exponentiation：

 
(define (make-exponentiation m1 m2) (list '** m1 m2))
​
; 期待返回 (** x 3)
(make-exponentiation 'x 3)
 
('** '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)
 
0

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

现在尝试直接计算：

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

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

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

现在修改一下和的表示：

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

 
(augend '(+ 2 3 4 5 6))
 
(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))
 
('* 2 3 4 5)

 
(multiplicand '(* 1 2))
 
2

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

 
(make-sum 'x 3)
 
('+ 'x 3)

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

再来计算一次：

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

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

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

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

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