Create a derivation program in lisp. 用 Lisp 写个求导程序

前言

记得之前看tensorflow, numpy等库的api中提供了自动求导的函数, 觉得其中一定是用了某些高深的数值分析算法，但在 sicp书中也给了个简单的求导程序, 本质是基于求导法则的递归性质来实现的， 感觉有点意思记录一下。

我们先来看看求导法则: 

1
2
3
4
dc / dx = 0
dx / dx = 1
d(u + v) / dx = du/dx + dv/dx
d(uv)/dx = u(dv/dx) + v(du/dv)

可以看到最后两条求导法则满足递归的性质, 求导的运算过程通过分解后会得到越来越小的片段，最终将产生出常量和变量, 他们的导数都是0或者1.

代码实现

首先我们定义谓语(返回值为bool的函数): 

1
2
3
4
5
6
7
8
9
(define (variable? x) (symbol? x)) ;判断是否为变量
(define (same-variable? v1 v2) ; 是否为同一变量?
    (and (variable? v1) (variable? v2) (eq? v1 v2)))

(define (sum? x) ; 是否为和式
    (and (pair? x) (eq? (car x) '+)))

(define (product? x) ; 是否为乘公式
    (and (pair? x) (eq? (car x) '*)))

然后我们需要定义出结果的构造方法: 

1
2
3
4
5
6
7
(define (make-sum a1 a2) (list '+ a1 a2)) ; 构造和式
(define (make-product a1 a2) (list '* a1 a2)) ; 构造乘式

(define (addend s) (cadr s)) ; 获取加数
(define (augend s) (caddr s)) ; 获取被加数
(define (multiplier p) (cadr p)) ; 获取乘数
(define (multiplicand p) (caddr p)) ; 获取被乘数

最后实现求导函数: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
(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: " exp))
    )
)

接下来我们可以测试一下: 

1
2
3
4
> (deriv '(* x 3) 'x)
(+ (* x 0) (* 1 3))
> (deriv '(+ x y) 'x)
(+ 1 0)

复杂D都得: 

1
2
> (deriv '(* (* x y) (+ x 3)) 'x)
(+ (* (* x y) (+ 1 0)) (* (+ (* x 0) (* 1 y)) (+ x 3)))

当然, 这个求导程序还是一个朴素的实现, 还需要对结果进行化简, 但是它已经实现了最核心的部分了…