The manipulation of symbolic algebraic expressions is a complex process that
illustrates many of the hardest problems that occur in the design of
large-scale systems. An algebraic expression, in general, can be viewed as a
hierarchical structure, a tree of operators applied to operands. We can
construct algebraic expressions by starting with a set of primitive objects,
such as constants and variables, and combining these by means of algebraic
operators, such as addition and multiplication. As in other languages, we form
abstractions that enable us to refer to compound objects in simple terms.
Typical abstractions in symbolic algebra are ideas such as linear combination,
polynomial, rational function, or trigonometric function. We can regard these
as compound “types,” which are often useful for directing the processing of
expressions. For example, we could describe the expression
x
2
符号代数表达式的处理是一个复杂的计算过程，体现了大规模系统设计中最棘手的诸多问题。一般而言，代数表达式可以看作一种层次结构——运算符作用于运算对象所形成的树。我们可以从一组基本对象（如常量和变量）出发，通过代数运算符（如加法和乘法）将它们组合起来，从而构造代数表达式。与其他语言一样，我们会形成各种抽象，使我们能够用简洁的方式引用复合对象。符号代数中典型的抽象概念包括：线性组合、多项式、有理函数、三角函数等。我们可以将这些看作复合的“类型”，它们对于指导表达式的处理过程往往非常有用。例如，表达式 x²
sin
(
sin(
y
2
y²
+
1
)
+ 1)
+
x
cos
2
y
x cos 2y
+
cos
(
cos(
y
3
y³
−
2
− 2
y
2
y²
)
as a polynomial in x with coefficients that are trigonometric functions of
polynomials in y whose coefficients are integers.
) 可以描述为：关于 x 的多项式，其系数是关于 y 的多项式的三角函数，而那些多项式的系数是整数。
We will not attempt to develop a complete algebraic-manipulation system here.
Such systems are exceedingly complex programs, embodying deep algebraic
knowledge and elegant algorithms. What we will do is look at a simple but
important part of algebraic manipulation: the arithmetic of polynomials. We
will illustrate the kinds of decisions the designer of such a system faces, and
how to apply the ideas of abstract data and generic operations to help organize
this effort.
Subheading: Arithmetic on polynomials
我们不打算在这里构建一个完整的代数操作系统。这类系统极为复杂，蕴含深刻的代数知识和精巧的算法。我们要做的是考察代数操作中一个简单却重要的部分：多项式的算术运算。我们将说明这类系统的设计者所面临的各种决策，以及如何运用数据抽象和通用操作的思想来帮助组织这一工作。
Our first task in designing a system for performing arithmetic on polynomials
is to decide just what a polynomial is. Polynomials are normally defined
relative to certain variables (the
indeterminates of the polynomial).
For simplicity, we will restrict ourselves to polynomials having just one
indeterminate (
univariate polynomials). We will define a polynomial to be a sum of terms, each of
which is either a coefficient, a power of the indeterminate, or a product of a
coefficient and a power of the indeterminate. A coefficient is defined as an
algebraic expression that is not dependent upon the indeterminate of the
polynomial. For example,
5
设计多项式算术系统的第一项任务是确定多项式究竟是什么。多项式通常是相对于某些变量（即多项式的不定元 (indeterminates)）来定义的。为了简单起见，我们将自己限制在只含一个不定元的多项式（单变元多项式 (univariate polynomials)）上。我们将多项式定义为若干项之和，每一项或为系数、或为不定元的幂次、或为系数与不定元幂次之积。系数被定义为不依赖于该多项式之不定元的代数表达式。例如，5
x
2
x²
+
3
x
3x
+
7
is a simple polynomial in x, and
(
+ 7 是关于 x 的一个简单多项式，而 (
y
2
y²
+
1
)
+ 1)
x
3
x³
+
(
2
y
)
x
+
1
is a polynomial in x whose coefficients are polynomials in y.
(2y) x + 1 则是关于 x 的多项式，其系数是关于 y 的多项式。
Already we are skirting some thorny issues. Is the first of these polynomials
the same as the polynomial 5
我们已经在触碰一些棘手的问题了。上面这两个多项式中的第一个，是否与多项式 5
y
2
y²
+
3
y
+
7, or not? A reasonable answer
might be “yes, if we are considering a polynomial purely as a mathematical
function, but no, if we are considering a polynomial to be a syntactic form.”
The second polynomial is algebraically equivalent to a polynomial in y
whose coefficients are polynomials in x. Should our system recognize this,
or not? Furthermore, there are other ways to represent a polynomial—for
example, as a product of factors, or (for a univariate polynomial) as the set
of roots, or as a listing of the values of the polynomial at a specified set of
points. We can finesse these questions by
deciding that in our algebraic-manipulation system a “polynomial” will be a
particular syntactic form, not its underlying mathematical meaning.
+ 3y + 7 相同？一个合理的回答可能是：“如果我们把多项式视为纯粹的数学函数，那么相同；如果我们把多项式视为一种语法形式，那么不同。”第二个多项式在代数上等价于一个关于 y 的多项式，其系数是关于 x 的多项式。我们的系统是否应该识别这一点？此外，表示多项式还有其他方式——例如，表示为因式之积，或（对于单变元多项式）表示为根的集合，或表示为多项式在一组指定点处取值的列表。我们可以通过以下决定来回避这些问题：在我们的代数操作系统中，“多项式”是一种特定的语法形式，而非其背后的数学含义。
Now we must consider how to go about doing arithmetic on polynomials. In this
simple system, we will consider only addition and multiplication. Moreover, we
will insist that two polynomials to be combined must have the same
indeterminate.
现在我们必须考虑如何对多项式进行算术运算。在这个简单系统中，我们只考虑加法和乘法。此外，我们还要求参与运算的两个多项式必须具有相同的不定元。
We will approach the design of our system by following the familiar discipline
of data abstraction. We will represent polynomials using a data structure
called a
poly, which consists of a variable and a collection of
terms. We assume that we have selectors variable and term-list
that extract those parts from a poly and a constructor make-poly that
assembles a poly from a given variable and a term list. A variable will be
just a symbol, so we can use the same-variable? procedure of
2.3.2 to compare variables. The following procedures define addition and
multiplication of polys:
我们将遵循熟悉的数据抽象规范来设计系统。我们用一种名为 poly 的数据结构来表示多项式，它由一个变量和一组项构成。我们假设已有选择函数 variable 和 term-list 用于从 poly 中提取这两部分，以及构造函数 make-poly 用于从给定的变量和项表组装一个 poly。变量就是一个符号 (symbol)，因此我们可以使用 2.3.2 节中的 same-variable? 过程来比较变量。以下过程定义了 poly 的加法和乘法：
To incorporate polynomials into our generic arithmetic system, we need to
supply them with type tags. We’ll use the tag polynomial, and install
appropriate operations on tagged polynomials in the operation table. We’ll
embed all our code in an installation procedure for the polynomial package,
similar to the ones in 2.5.1:
为了将多项式纳入我们的通用算术系统，需要为其附上类型标签。我们使用标签 polynomial，并在操作表中为带标签的多项式安装相应的操作。我们将把所有代码嵌入多项式包的安装过程中，形式类似于 2.5.1 节中的各安装过程：
Polynomial addition is performed termwise. Terms of the same order (i.e., with
the same power of the indeterminate) must be combined. This is done by forming
a new term of the same order whose coefficient is the sum of the coefficients
of the addends. Terms in one addend for which there are no terms of the same
order in the other addend are simply accumulated into the sum polynomial being
constructed.
多项式的加法按逐项进行。同阶的项（即不定元的幂次相同的项）必须合并。合并的方式是：构造一个同阶的新项，其系数为被加数对应系数之和。若某个被加数中有某些项在另一个被加数中找不到同阶的对应项，则将这些项直接累积到正在构造的和多项式中。
In order to manipulate term lists, we will assume that we have a constructor
the-empty-termlist that returns an empty term list and a constructor
adjoin-term that adjoins a new term to a term list. We will also assume
that we have a predicate empty-termlist? that tells if a given term list
is empty, a selector first-term that extracts the highest-order term
from a term list, and a selector rest-terms that returns all but the
highest-order term. To manipulate terms, we will suppose that we have a
constructor make-term that constructs a term with given order and
coefficient, and selectors order and coeff that return,
respectively, the order and the coefficient of the term. These operations
allow us to consider both terms and term lists as data abstractions, whose
concrete representations we can worry about separately.
为了操作项表，我们假设已有构造函数 the-empty-termlist 用于返回一个空项表，以及构造函数 adjoin-term 用于将一个新项加入项表。我们还假设已有谓词 empty-termlist? 用于判断给定项表是否为空，选择函数 first-term 用于从项表中提取最高阶项，以及选择函数 rest-terms 用于返回除最高阶项之外的其余所有项。为了操作项，我们假设已有构造函数 make-term 用于构造一个具有给定阶数和系数的项，以及选择函数 order 和 coeff 分别用于返回项的阶数和系数。这些操作使我们能够把项和项表都视为数据抽象，其具体表示可以单独考虑。
Here is the procedure that constructs the term list for the sum of two
polynomials:
下面是构造两个多项式之和的项表的过程：
The most important point to note here is that we used the generic addition
procedure add to add together the coefficients of the terms being
combined. This has powerful consequences, as we will see below.
此处最值得注意的是：我们使用通用加法过程 add 来对被合并的各项的系数求和。这具有深远的意义，我们将在下文中看到。
In order to multiply two term lists, we multiply each term of the first list by
all the terms of the other list, repeatedly using mul-term-by-all-terms,
which multiplies a given term by all terms in a given term list. The resulting
term lists (one for each term of the first list) are accumulated into a sum.
Multiplying two terms forms a term whose order is the sum of the orders of the
factors and whose coefficient is the product of the coefficients of the
factors:
为了将两个项表相乘，我们用第一个表中的每一项乘以另一个表中的所有项，反复使用 mul-term-by-all-terms 过程——该过程将给定的一项与给定项表中的所有项相乘。所得到的各个项表（第一个表中每一项对应一个）被累积合并成一个和。两项相乘所得到的新项，其阶数为两因子阶数之和，其系数为两因子系数之积：
This is really all there is to polynomial addition and multiplication. Notice
that, since we operate on terms using the generic procedures add and
mul, our polynomial package is automatically able to handle any type of
coefficient that is known about by the generic arithmetic package. If we
include a coercion mechanism such as one of those discussed in
2.5.2, then we also are automatically able to handle operations on
polynomials of different coefficient types, such as
[
3
以上就是多项式加法和乘法的全部内容。注意，由于我们通过通用过程 add 和 mul 对项进行运算，我们的多项式包能够自动处理通用算术包所知道的任何类型的系数。如果我们加入 2.5.2 节中讨论的某种强制转换机制，那么我们还能自动处理不同系数类型的多项式之间的运算，例如 [3
x
2
x²
+
(
2
+
3
i
)
x
+
7
]
⋅
+ (2 + 3i) x + 7] ⋅
[
x
4
+
2
3
x
2
+
(
5
+
3
i
)
]
.
Because we installed the polynomial addition and multiplication procedures
add-poly and mul-poly in the generic arithmetic system as the
add and mul operations for type polynomial, our system is
also automatically able to handle polynomial operations such as
[
。
由于我们已将多项式加法和乘法过程 add-poly 与 mul-poly 作为类型 polynomial 的 add 和 mul 操作安装到通用算术系统中，系统也就自动地能够处理如下多项式运算：
[
(
y
+
1
)
x
2
+
(
y
2
+
1
)
x
+
(
y
−
1
)
]
⋅
[
(
y
−
2
)
x
+
(
y
3
+
7
)
]
.
The reason is that when the system tries to combine coefficients, it will
dispatch through add and mul. Since the coefficients are
themselves polynomials (in y), these will be combined using add-poly
and mul-poly. The result is a kind of “data-directed recursion” in
which, for example, a call to mul-poly will result in recursive calls to
mul-poly in order to multiply the coefficients. If the coefficients of
the coefficients were themselves polynomials (as might be used to represent
polynomials in three variables), the data direction would ensure that the
system would follow through another level of recursive calls, and so on through
as many levels as the structure of the data dictates.
Subheading: Representing term lists
。
原因在于：当系统试图合并系数时，会通过 add 和 mul 进行分派。由于系数本身是（关于 y 的）多项式，它们将由 add-poly 和 mul-poly 完成合并。其结果是一种"数据导向的递归"——例如，对 mul-poly 的一次调用将递归地调用 mul-poly 来完成系数的相乘。若系数的系数本身也是多项式（这可用于表示三个变量的多项式），数据导向机制会确保系统沿着递归调用再深入一层，如此层层递进，直至数据结构所规定的深度为止。
子标题：项表的表示
Finally, we must confront the job of implementing a good representation for
term lists. A term list is, in effect, a set of coefficients keyed by the
order of the term. Hence, any of the methods for representing sets, as
discussed in 2.3.3, can be applied to this task. On the other
hand, our procedures add-terms and mul-terms always access term
lists sequentially from highest to lowest order. Thus, we will use some kind
of ordered list representation.
最后，我们必须正视如何为项表实现一种良好表示的任务。项表 (term list) 实质上是一组以项的阶次为键的系数集合。因此，2.3.3 节中讨论的任何集合表示方法都可以应用于此任务。另一方面，我们的过程 add-terms 和 mul-terms 总是按从高阶到低阶的顺序依次访问项表。为此，我们将采用某种有序表的表示形式。
How should we structure the list that represents a term list? One
consideration is the “density” of the polynomials we intend to manipulate. A
polynomial is said to be
dense if it has nonzero coefficients in
terms of most orders. If it has many zero terms it is said to be
我们应当如何构造表示项表的表？一个需要考量的因素是我们打算处理的多项式的"密度"。若一个多项式在大多数阶次上都有非零系数，则称它是稠密的 (dense)；若其中有许多零次项，则称它是
sparse. For example,
A
:
稀疏的 (sparse)。例如，
A
：
x
5
+
2
x
4
+
3
x
2
−
2
x
−
5
is a dense polynomial, whereas
B
:
−
5
是一个稠密多项式，而
B
：
x
100
+
2
x
2
+
1
is sparse.
+
1
是稀疏的。
The term lists of dense polynomials are most efficiently represented as lists
of the coefficients. For example, A above would be nicely represented as
(1 2 0 3 -2 -5). The order of a term in this representation is the
length of the sublist beginning with that term’s coefficient, decremented by
1. This would be a terrible representation for
a sparse polynomial such as B: There would be a giant list of zeros
punctuated by a few lonely nonzero terms. A more reasonable representation of
the term list of a sparse polynomial is as a list of the nonzero terms, where
each term is a list containing the order of the term and the coefficient for
that order. In such a scheme, polynomial B is efficiently represented as
((100 1) (2 2) (0 1)). As most polynomial manipulations are performed
on sparse polynomials, we will use this method. We will assume that term lists
are represented as lists of terms, arranged from highest-order to lowest-order
term. Once we have made this decision, implementing the selectors and
constructors for terms and term lists is straightforward:
稠密多项式的项表最适合用系数的表来表示。例如，上面的多项式 A 可以很方便地表示为 (1 2 0 3 -2 -5)。在这种表示中，某一项的阶数等于以该项系数为起点的子表的长度减一。然而对于稀疏多项式（如 B）而言，这将是一种极糟糕的表示方式：表中将充斥着大量的零，仅有寥寥几个非零项点缀其间。稀疏多项式项表更合理的表示方式，是以非零项的表来描述，其中每一项本身是一个包含该项阶数和系数的表。在这种方案下，多项式 B 可以高效地表示为 ((100 1) (2 2) (0 1))。由于大多数多项式运算都针对稀疏多项式，我们将采用这一方法。我们假设项表以项的表的形式表示，并按从高阶到低阶的顺序排列。一旦做出这一决定，实现项与项表的选择函数和构造函数便是直截了当的：
where =zero? is as defined in Exercise 2.80. (See also
Exercise 2.87 below.)
其中 =zero? 如练习 2.80 中所定义。（另见下面的练习 2.87。）
Users of the polynomial package will create (tagged) polynomials by means of
the procedure:
多项式程序包的用户将通过以下过程创建（带标签的）多项式：
(define (add-poly p1 p2)
(if (same-variable? (variable p1)
(variable p2))
(make-poly
(variable p1)
(add-terms (term-list p1)
(term-list p2)))
(error "Polys not in same var:
ADD-POLY"
(list p1 p2))))
(define (mul-poly p1 p2)
(if (same-variable? (variable p1)
(variable p2))
(make-poly
(variable p1)
(mul-terms (term-list p1)
(term-list p2)))
(error "Polys not in same var:
MUL-POLY"
(list p1 p2))))(define (install-polynomial-package)
;; internal procedures
;; representation of poly
(define (make-poly variable term-list)
(cons variable term-list))
(define (variable p) (car p))
(define (term-list p) (cdr p))
⟨procedures same-variable?
and variable? from section 2.3.2⟩
;; representation of terms and term lists
⟨procedures adjoin-term … coeff
from text below⟩
(define (add-poly p1 p2) …)
⟨procedures used by add-poly⟩
(define (mul-poly p1 p2) …)
⟨procedures used by mul-poly⟩
;; interface to rest of the system
(define (tag p) (attach-tag 'polynomial p))
(put 'add '(polynomial polynomial)
(lambda (p1 p2)
(tag (add-poly p1 p2))))
(put 'mul '(polynomial polynomial)
(lambda (p1 p2)
(tag (mul-poly p1 p2))))
(put 'make 'polynomial
(lambda (var terms)
(tag (make-poly var terms))))
'done)(define (add-terms L1 L2)
(cond ((empty-termlist? L1) L2)
((empty-termlist? L2) L1)
(else
(let ((t1 (first-term L1))
(t2 (first-term L2)))
(cond ((> (order t1) (order t2))
(adjoin-term
t1
(add-terms (rest-terms L1)
L2)))
(( (order t1) (order t2))
(adjoin-term
t2
(add-terms
L1
(rest-terms L2))))
(else
(adjoin-term
(make-term
(order t1)
(add (coeff t1)
(coeff t2)))
(add-terms
(rest-terms L1)
(rest-terms L2)))))))))(define (mul-terms L1 L2)
(if (empty-termlist? L1)
(the-empty-termlist)
(add-terms
(mul-term-by-all-terms
(first-term L1) L2)
(mul-terms (rest-terms L1) L2))))
(define (mul-term-by-all-terms t1 L)
(if (empty-termlist? L)
(the-empty-termlist)
(let ((t2 (first-term L)))
(adjoin-term
(make-term
(+ (order t1) (order t2))
(mul (coeff t1) (coeff t2)))
(mul-term-by-all-terms
t1
(rest-terms L))))))(define (adjoin-term term term-list)
(if (=zero? (coeff term))
term-list
(cons term term-list)))
(define (the-empty-termlist) '())
(define (first-term term-list) (car term-list))
(define (rest-terms term-list) (cdr term-list))
(define (empty-termlist? term-list)
(null? term-list))
(define (make-term order coeff)
(list order coeff))
(define (order term) (car term))
(define (coeff term) (cadr term))(define (make-polynomial var terms)
((get 'make 'polynomial) var terms))