在Racket中使用分派表

Question

我正在编写一个小程序来计算以列表形式表示的表达式的简单导数，例如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的函数，它接受一个方程（以列表形式表示），并计算对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）

- kfem

Answer 1

在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过程正是为了在这样的列表中查找数据而设计的。您可以在文档中了解更多信息。

- Óscar López

Answer 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

- dyoo