Exercise 2.91 · 习题

Exercise 2.91: A univariate polynomial can be
divided by another one to produce a polynomial quotient and a polynomial
remainder. For example,
x
5

−
1

x
2

−
1

=

x
3

+
x
,

remainder

x
−
1.
Division can be performed via long division. That is, divide the highest-order
term of the dividend by the highest-order term of the divisor. The result is
the first term of the quotient. Next, multiply the result by the divisor,
subtract that from the dividend, and produce the rest of the answer by
recursively dividing the difference by the divisor. Stop when the order of the
divisor exceeds the order of the dividend and declare the dividend to be the
remainder. Also, if the dividend ever becomes zero, return zero as both
quotient and remainder.

We can design a div-poly procedure on the model of add-poly and
mul-poly. The procedure checks to see if the two polys have the same
variable. If so, div-poly strips off the variable and passes the
problem to div-terms, which performs the division operation on term
lists. Div-poly finally reattaches the variable to the result supplied
by div-terms. It is convenient to design div-terms to compute
both the quotient and the remainder of a division. Div-terms can take
two term lists as arguments and return a list of the quotient term list and the
remainder term list.

Complete the following definition of div-terms by filling in the missing
expressions. Use this to implement div-poly, which takes two polys as
arguments and returns a list of the quotient and remainder polys.

(define (div-terms L1 L2)
(if (empty-termlist? L1)
(list (the-empty-termlist)
(the-empty-termlist))
(let ((t1 (first-term L1))
(t2 (first-term L2)))
(if (> (order t2) (order t1))
(list (the-empty-termlist) L1)
(let ((new-c (div (coeff t1)
(coeff t2)))
(new-o (- (order t1)
(order t2))))
(let ((rest-of-result
⟨compute rest of result
recursively⟩ ))
⟨form complete result⟩ ))))))

Hierarchies of types in symbolic algebra

Our polynomial system illustrates how objects of one type (polynomials) may in
fact be complex objects that have objects of many different types as parts.
This poses no real difficulty in defining generic operations. We need only
install appropriate generic operations for performing the necessary
manipulations of the parts of the compound types. In fact, we saw that
polynomials form a kind of “recursive data abstraction,” in that parts of a
polynomial may themselves be polynomials. Our generic operations and our
data-directed programming style can handle this complication without much
trouble.

On the other hand, polynomial algebra is a system for which the data types
cannot be naturally arranged in a tower. For instance, it is possible to have
polynomials in x whose coefficients are polynomials in y. It is also
possible to have polynomials in y whose coefficients are polynomials in
x. Neither of these types is “above” the other in any natural way, yet
it is often necessary to add together elements from each set. There are
several ways to do this. One possibility is to convert one polynomial to the
type of the other by expanding and rearranging terms so that both polynomials
have the same principal variable. One can impose a towerlike structure on this
by ordering the variables and thus always converting any polynomial to a
“canonical form” with the highest-priority variable dominant and the
lower-priority variables buried in the coefficients. This strategy works
fairly well, except that the conversion may expand a polynomial unnecessarily,
making it hard to read and perhaps less efficient to work with. The tower
strategy is certainly not natural for this domain or for any domain where the
user can invent new types dynamically using old types in various combining
forms, such as trigonometric functions, power series, and integrals.

It should not be surprising that controlling coercion is a serious problem in

the design of large-scale algebraic-manipulation systems. Much of the

complexity of such systems is concerned with relationships among diverse types.

Indeed, it is fair to say that we do not yet completely understand coercion.

In fact, we do not yet completely understand the concept of a data type.

Nevertheless, what we know provides us with powerful structuring and modularity

principles to support the design of large systems.

练习 2.91：一个单变量多项式可以被另一个整除，得到多项式商和多项式余式。例如，

x⁵ − 1

──────

x² − 1

= x³ + x，余式 x − 1。

除法可以通过长除法来完成。即：用被除式的最高次项除以除式的最高次项，结果即为商的第一项；然后将该结果乘以除式，从被除式中减去，再对差式与除式递归地进行除法，得到商的其余部分。当除式的阶数超过被除式时停止，并将此时的被除式声明为余式。此外，若被除式在某一步变为零，则以零作为商和余式返回。

我们可以仿照 add-poly 和 mul-poly 的模式设计 div-poly 过程。该过程检查两个多项式是否具有相同的变量；若是，div-poly 剥去变量后将问题交给 div-terms 处理，后者对项表执行除法操作；div-poly 最后将 div-terms 返回的结果重新附上变量。将 div-terms 设计为同时计算商和余式会比较方便。div-terms 接受两个项表作为参数，返回由商项表和余式项表组成的表。

通过填入缺失的表达式来完成 div-terms 的如下定义。并用此实现 div-poly，它接受两个多项式作为参数，返回由商多项式和余式多项式组成的表。

(define (div-terms L1 L2)
(if (empty-termlist? L1)
(list (the-empty-termlist)
(the-empty-termlist))
(let ((t1 (first-term L1))
(t2 (first-term L2)))
(if (> (order t2) (order t1))
(list (the-empty-termlist) L1)
(let ((new-c (div (coeff t1)
(coeff t2)))
(new-o (- (order t1)
(order t2))))
(let ((rest-of-result
⟨compute rest of result
recursively⟩ ))
⟨form complete result⟩ ))))))

符号代数中的类型层次结构

我们的多项式系统说明了，某一类型的对象（多项式）实际上可以是将许多不同类型的对象作为组成部分的复合对象。这在定义通用操作时并不构成真正的困难——我们只需为操作复合类型各部分所必须的操作安装适当的通用过程即可。事实上，我们看到多项式构成了一种"递归数据抽象"：多项式的各项系数本身也可以是多项式。我们的通用操作和数据导向编程风格可以毫无困难地处理这种复杂性。

另一方面，多项式代数是一个数据类型无法自然排列成塔状结构的系统。例如，系数为关于 y 的多项式的关于 x 的多项式是可能存在的；系数为关于 x 的多项式的关于 y 的多项式也是可能存在的。这两种类型在任何自然的意义上都不比另一种更"高"，然而往往需要对来自两个集合的元素进行加法。处理这一问题有若干方法。一种可能是通过展开和重新排列各项，将一个多项式转换为另一个多项式的类型，使两个多项式具有相同的主变量。可以通过对变量排序来将此过程强加一种塔状结构，从而始终将任意多项式转换为以最高优先级变量为主、低优先级变量埋入系数的"规范形式"。这种策略效果尚可，但转换可能会不必要地展开多项式，使其难以阅读，处理效率也可能降低。对于多项式这一领域，或任何用户可以用旧类型的各种组合形式（如三角函数、幂级数和积分）动态发明新类型的领域，塔状策略显然都不够自然。

在大型代数操控系统的设计中，强制转换的控制是一个严峻问题，这并不奇怪。这类系统的复杂性很大程度上源于各种类型之间的关系。事实上，可以说我们对强制转换的理解至今仍不完整。实际上，我们对数据类型这一概念本身的理解也尚不完整。尽管如此，我们所掌握的知识已能为大型系统的设计提供强有力的结构化和模块化原则。