3

我正在编写一个小程序来计算以列表形式表示的表达式的简单导数，即2x^2表示为(* 2 (exp x 2))，我定义了以下函数：

;; derivative of a constant is 0
(define (diff-constant x E) 0)

;; computes derivative of E with respect to x where E can only be of the form
;; (+ x x ...)
(define (diff-sum x E)
  (cond ((or (not (list? E)) (null? E)) 0)
        ((eq? (car E) x) (+ 1 (diff-sum x (cdr E))))
        (else (diff-sum x (cdr E)))))

;; computes derivative of E with respect to x where E can only be of the form
;; (* x y)
(define (diff-product x E)
  (cond ((and (eq? x (cadr E)) (eq? x (caddr E))) (list '* 2 x))
        ((eq? x (cadr E)) (list (caddr E)))
        ((eq? x (caddr E)) (list (cadr E)))
        (else 0)))

;; computes derivative of E with respect to x where E can only be of the form
;; (expt x y) which is x^y
(define (diff-expt x E)
  (cond ( not (eq? x (cadr E)) 0)
        ((eq? 1 (caddr E)) 0)
        ((eq? 2 (caddr E)) (cadr E))
        (else (list '* (caddr E) (list 'expt x (- (caddr E) 1))))))

我还有一个调度表定义为：

;; Dispatch Table of supported operators.
 (define diff-dispatch
   (list (list '+ diff-sum)
         (list '* diff-product)
         (list 'expt diff-expt)
         ))

我正在尝试编写一个函数，该函数diff采用一个方程E（以列表形式）并计算相对于的导数x并使用调度表调用返回结果的预定义函数

这是我到目前为止所拥有的，但我无法弄清楚其余的

;; Differentiate expression E with respect to x.
(define (diff x E)
  (cond ((number? E) (diff-constant x E))
        ;; insert code here to handle the other base case - variables
        ...
        (else    ; insert code here to lookup the appropriate function in the
                 ; dispatch table based on the operator in the expression,
                 ; then call that function to differentiate the expression
                     (diff-func x E))))))

例如：(diff 'x '(+ x (* x x)))应该评估为(+ 1 (+ (* 1 (* x)) (* x 1)))（即 1 + x + x）

4

2 回答 2

2

在SICP 书中有一整节详细解释了如何构建用于执行符号微分的 Scheme 程序，请查看第 2.3 节。特别是，请注意您遗漏了一种情况 - 如果要派生的表达式是变量会发生什么？检查链接以确保您在正确的轨道上。

现在，回答这个问题：给定代码中使用的表表示，实现调度程序很简单。这些方面的东西将有助于获得应用正确的微分程序：

((cadr             ; obtain the differentiation procedure
  (assoc           ; look for the differentiation procedure
   (car E)         ; obtain the operator in the expression
   diff-dispatch)) ; dispatch table
 x E)              ; apply the procedure with parameters `x` and `E`

请注意，找到要应用的正确过程的“诀窍”在于该表是作为关联列表实现的，并且该assoc过程是为在此类列表中查找数据而精确设计的。在文档中阅读有关它的更多信息。

于 2012-10-17T23:32:43.197 回答
2

补充一下 Óscar López 的回答：在专业级的 Racket 程序中，我们希望尽可能快地进行调度。如果要测试的事物数量超过几个项目，我们可能应该使用支持快速查找的数据结构，例如向量或哈希表。数据表示很重要：列表不是我们应该知道的最好或唯一的数据结构。SICP 偏向于对所有事物使用链表表示是值得称赞的。但有时链表不是正确的结构。

在基于哈希表的方法中，调度表的设置非常相似：

;; in professional-level Racket (#lang racket)
(define dispatch-table (hash '+ diff-sum
                             '* diff-product
                             ;; ... etc
                             ))

查找表是一个散列引用。

(define op '+)
(hash-ref dispatch-table op)      ;;; => diff-sum
于 2012-10-18T17:40:23.103 回答