2.3.2 Example: Symbolic Differentiation

As an illustration of symbol manipulation and a further illustration of data

abstraction, consider the design of a procedure that performs symbolic

differentiation of algebraic expressions. We would like the procedure to take

as arguments an algebraic expression and a variable and to return the

derivative of the expression with respect to the variable. For example, if the

arguments to the procedure are a

作为符号操作的示例，同时也是数据抽象的进一步说明，我们来考察这样一个过程的设计：对代数表达式执行符号微分 (symbolic differentiation)。我们希望该过程以一个代数表达式和一个变量为参数，返回表达式对该变量的导数。例如，若过程的参数为

x
2

+

b

x

+

c and x, the

procedure should return 2

a

x

+

b. Symbolic differentiation is of

special historical significance in Lisp. It was one of the motivating examples

behind the development of a computer language for symbol manipulation.

Furthermore, it marked the beginning of the line of research that led to the

development of powerful systems for symbolic mathematical work, which are

currently being used by a growing number of applied mathematicians and

physicists.

+

b

x

+

c 与 x，则过程应返回 2

a

x

+

b。符号微分在 Lisp 的历史上具有重要意义。它是推动计算机语言用于符号操作这一研究方向的动机之一。此外，它标志着一条研究路线的起点，这条路线最终催生了功能强大的符号数学工作系统，目前越来越多的应用数学家和物理学家正在使用这些系统。

In developing the symbolic-differentiation program, we will follow the same

strategy of data abstraction that we followed in developing the rational-number

system of 2.1.1. That is, we will first define a differentiation

algorithm that operates on abstract objects such as “sums,” “products,” and

“variables” without worrying about how these are to be represented. Only

afterward will we address the representation problem.

Subheading: The differentiation program with abstract data

在开发符号微分程序的过程中，我们将遵循与 2.1.1 节开发有理数系统时相同的数据抽象策略。也就是说，我们首先定义一个作用于抽象对象（如"和式"、"积式"和"变量"）的微分算法，而不必考虑这些对象如何表示；之后才处理表示问题。

小节标题：基于抽象数据的微分程序

In order to keep things simple, we will consider a very simple

symbolic-differentiation program that handles expressions that are built up

using only the operations of addition and multiplication with two arguments.

Differentiation of any such expression can be carried out by applying the

following reduction rules:

d

c

为了简单起见，我们考虑一个非常简单的符号微分程序，它处理的表达式仅由加法和乘法两种运算（各带两个参数）构成。对任何此类表达式的微分，都可以通过运用以下化简规则来实现：

d

c

d
x

=

0
,
0
，

for

c

a constant

其中

c

为常数

or a variable

或与

different from

x

,

d

x

x

不同的变量，

d

x

d
x

=

1
,
1
，

d
(
u
+
v
)

d
x

=

d
u

d
x

+

d
v

d
x

,
，

d
(
u
v
)

d
x

=

u

d
v

d
x

+
v

d
u

d
x

.

Observe that the latter two rules are recursive in nature. That is, to obtain

the derivative of a sum we first find the derivatives of the terms and add

them. Each of the terms may in turn be an expression that needs to be

decomposed. Decomposing into smaller and smaller pieces will eventually

produce pieces that are either constants or variables, whose derivatives will

be either 0 or 1.

。

注意后两条规则在本质上是递归的。即，要求一个和式的导数，需先求各加项的导数，再将结果相加。每个加项本身又可能是需要进一步分解的表达式。不断地分解成更小的片段，最终将得到常量或变量，其导数分别为 0 或 1。

To embody these rules in a procedure we indulge in a little wishful thinking,

as we did in designing the rational-number implementation. If we had a means

for representing algebraic expressions, we should be able to tell whether an

expression is a sum, a product, a constant, or a variable. We should be able

to extract the parts of an expression. For a sum, for example we want to be

able to extract the addend (first term) and the augend (second term). We

should also be able to construct expressions from parts. Let us assume that we

already have procedures to implement the following selectors, constructors, and

predicates:

为了将这些规则体现在一个过程中，我们像设计有理数实现时那样，纵情发挥一番一厢情愿的想象。若我们有一种表示代数表达式的方法，就能判断一个表达式是和式、积式、常量还是变量，也能抽取表达式的各个组成部分。以和式为例，我们希望能够提取被加数（addend，第一项）和加数（augend，第二项）。此外，我们还应能够从各部分重新构造表达式。现假定我们已有过程来实现如下选择函数、构造函数和谓词：

Using these, and the primitive predicate number?, which identifies

numbers, we can express the differentiation rules as the following procedure:

利用这些过程，以及能识别数的基本谓词 `number?`，可以将求导规则表达为如下过程：

This deriv procedure incorporates the complete differentiation

algorithm. Since it is expressed in terms of abstract data, it will work no

matter how we choose to represent algebraic expressions, as long as we design a

proper set of selectors and constructors. This is the issue we must address

next.

Subheading: Representing algebraic expressions

这个 `deriv` 过程包含了完整的求导算法。由于它是用抽象数据来表达的，无论我们选择何种方式表示代数表达式，只要设计出一套合适的选择函数和构造函数，它都能正常工作。这正是我们接下来必须解决的问题。

小节标题：代数表达式的表示

We can imagine many ways to use list structure to represent algebraic

expressions. For example, we could use lists of symbols that mirror the usual

algebraic notation, representing a

x

+

b as the list (a * x + b).

However, one especially straightforward choice is to use the same

parenthesized prefix notation that Lisp uses for combinations; that is, to

represent a

x

+

b as (+ (* a x) b). Then our data

representation for the differentiation problem is as follows:

我们可以设想用表结构表示代数表达式的多种方式。例如，可以用镜像惯常代数记法的符号表来表示，将 a x + b 表示为表 `(a * x + b)`。然而，有一种特别直接的选择：使用 Lisp 用于组合式的带括号前缀记法——即把 a x + b 表示为 `(+ (* a x) b)`。这样，求导问题的数据表示如下：

The variables are symbols. They are identified by the primitive predicate

symbol?:

变量是符号，由基本谓词 `symbol?` 来识别：

(define (variable? x) (symbol? x))

Two variables are the same if the symbols representing them are eq?:

若表示两个变量的符号满足 `eq?`，则这两个变量相同：

(define (same-variable? v1 v2)
(and (variable? v1)
(variable? v2)
(eq? v1 v2)))

Sums and products are constructed as lists:

和式与积式由表来构造：

(define (make-sum a1 a2) (list '+ a1 a2))
(define (make-product m1 m2) (list '* m1 m2))

A sum is a list whose first element is the symbol +:

和式是以符号 `+` 为第一个元素的表：

(define (sum? x)
(and (pair? x) (eq? (car x) '+)))

The addend is the second item of the sum list:

被加数是和式表的第二个元素：

(define (addend s) (cadr s))

The augend is the third item of the sum list:

加数是和式表的第三个元素：

(define (augend s) (caddr s))

A product is a list whose first element is the symbol *:

积式是以符号 `*` 为第一个元素的表：

(define (product? x)
(and (pair? x) (eq? (car x) '*)))

The multiplier is the second item of the product list:

被乘数是积式表的第二个元素：

(define (multiplier p) (cadr p))

The multiplicand is the third item of the product list:

乘数是积式表的第三个元素：

(define (multiplicand p) (caddr p))

Thus, we need only combine these with the algorithm as embodied by deriv

in order to have a working symbolic-differentiation program. Let us look at

some examples of its behavior:

这样，我们只需将这些选择函数与 deriv 所体现的算法结合起来，便可得到一个能正常工作的符号微分程序。下面来看几个运行示例：

The program produces answers that are correct; however, they are unsimplified.

It is true that

d

(

x

y

)

程序给出的答案是正确的，但尚未化简。确实，

d
x

=

x
⋅
0

+

1

⋅

y

,

but we would like the program to know that x

⋅

0

=

0, 1

⋅

y

=

y,

and 0

+

y

=

y. The answer for the second example should have been

simply y. As the third example shows, this becomes a serious issue when

the expressions are complex.

1

⋅

y

是成立的，但我们希望程序能知道 x

⋅

0

=

0、1

⋅

y

=

y，以及 0

+

y

=

y。第二个例子的答案本应直接是 y。正如第三个例子所示，当表达式变得复杂时，这一问题便愈发严重。

Our difficulty is much like the one we encountered with the rational-number

implementation: we haven’t reduced answers to simplest form. To accomplish the

rational-number reduction, we needed to change only the constructors and the

selectors of the implementation. We can adopt a similar strategy here. We

won’t change deriv at all. Instead, we will change make-sum so

that if both summands are numbers, make-sum will add them and return

their sum. Also, if one of the summands is 0, then make-sum will return

the other summand:

我们面临的困难与处理有理数实现时遇到的问题如出一辙：没有将结果化简为最简形式。当时为了实现有理数的化简，只需修改实现中的构造函数和选择函数即可。这里可以采用类似的策略。我们完全不改动 deriv，而是修改 make-sum：若两个被加数都是数，make-sum 就直接将它们相加并返回其和；若其中一个被加数为 0，则 make-sum 返回另一个被加数：

This uses the procedure =number?, which checks whether an expression is

equal to a given number:

这里用到了过程 =number?，它检验一个表达式是否等于某个给定的数：

Similarly, we will change make-product to build in the rules that 0

times anything is 0 and 1 times anything is the thing itself:

类似地，我们修改 make-product，将“0 乘以任何数得 0”和“1 乘以任何数得其本身”这两条规则内建其中：

Here is how this version works on our three examples:

下面是这个新版本在三个例子上的运行结果：

Although this is quite an improvement, the third example shows that there is

still a long way to go before we get a program that puts expressions into a

form that we might agree is “simplest.” The problem of algebraic

simplification is complex because, among other reasons, a form that may be

simplest for one purpose may not be for another.

虽然这已是相当大的改进，但第三个例子表明，距离我们所期待的“最简形式”还相去甚远。代数化简之所以复杂，原因之一在于：对于某一目的而言最简的形式，对于另一目的却未必如此。