content/book-Z-H-18.html

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN" "http:https://www.w3.org/TR/REC-html40/loose.dtd">

<html>
<!-- Generated from TeX source by tex2page, v 4o, 
     (c) Dorai Sitaram, http:https://www.cs.rice.edu/~dorai/tex2page -->

<head>
  <meta name="generator" content="HTML Tidy for Linux (vers 7 December 2008), see www.w3.org" />

  <title>Structure and Interpretation of Computer Programs</title>
  <link href="book-Z-C.css" title="default" rel="stylesheet" type="text/css" />
  <meta name="robots" content="noindex,follow" />
</head>

<body>
  <mbp:pagebreak />

  <p><a name="%_sec_2.5"></a></p>

  <h2><a href="book-Z-H-4.html#%_toc_%_sec_2.5">2.5&nbsp;&nbsp;Systems with
  Generic Operations</a></h2>

  <p><a name="%_idx_2496"></a>In the previous section, we saw how
  to design systems in which data objects can be represented in
  more than one way. The key idea is to link the code that
  specifies the data operations to the several representations by
  means of generic interface procedures. Now we will see how to use
  this same idea not only to define operations that are generic
  over different representations but also to define operations that
  are generic over different kinds of arguments. We have already
  seen several different packages of arithmetic operations: the
  primitive arithmetic (<tt>+</tt>, <tt>-</tt>, <tt>*</tt>,
  <tt>/</tt>) built into our language, the rational-number
  arithmetic (<tt>add-rat</tt>, <tt>sub-rat</tt>, <tt>mul-rat</tt>,
  <tt>div-rat</tt>) of section&nbsp;<a href="book-Z-H-14.html#%_sec_2.1.1">2.1.1</a>, and the complex-number
  arithmetic that we implemented in section&nbsp;<a href="book-Z-H-17.html#%_sec_2.4.3">2.4.3</a>. We will now use
  data-directed techniques to construct a package of arithmetic
  operations that incorporates all the arithmetic packages we have
  already constructed.</p>

  <p>Figure&nbsp;<a href="#%_fig_2.23">2.23</a> shows the structure
  of the system we shall build. Notice the <a name="%_idx_2498"></a>abstraction barriers. From the perspective of
  someone using ``numbers,'' there is a single procedure
  <tt>add</tt> that operates on whatever numbers are supplied.
  <tt>Add</tt> is part of a generic interface that allows the
  separate ordinary-arithmetic, rational-arithmetic, and
  complex-arithmetic packages to be accessed uniformly by programs
  that use numbers. Any individual arithmetic package (such as the
  complex package) may itself be accessed through generic
  procedures (such as <tt>add-complex</tt>) that combine packages
  designed for different representations (such as rectangular and
  polar). Moreover, the structure of the system is additive, so
  that one can design the individual arithmetic packages separately
  and combine them to produce a generic arithmetic system. <a name="%_fig_2.23"></a></p>

  <div align="left">
    <div align="left">
      <b>Figure 2.23:</b>&nbsp;&nbsp;Generic arithmetic system.
    </div>

    <table width="100%">
      <tr>
        <td><img src="ch2-Z-G-64.gif" border="0" /></td>
      </tr>

      <tr>
        <td><a name="%_idx_2500"></a></td>
      </tr>
    </table>
  </div>

  <p><a name="%_sec_2.5.1"></a></p>

  <h3><a href="book-Z-H-4.html#%_toc_%_sec_2.5.1">2.5.1&nbsp;&nbsp;Generic
  Arithmetic Operations</a></h3>

  <p><a name="%_idx_2502"></a> The task of designing generic
  arithmetic operations is analogous to that of designing the
  generic complex-number operations. We would like, for instance,
  to have a generic addition procedure <tt>add</tt> that acts like
  ordinary primitive addition <tt>+</tt> on ordinary numbers, like
  <tt>add-rat</tt> on rational numbers, and like
  <tt>add-complex</tt> on complex numbers. We can implement
  <tt>add</tt>, and the other generic arithmetic operations, by
  following the same strategy we used in section&nbsp;<a href="book-Z-H-17.html#%_sec_2.4.3">2.4.3</a> to implement the generic
  selectors for complex numbers. We will attach a type tag to each
  kind of number and cause the generic procedure to dispatch to an
  appropriate package according to the data type of its
  arguments.</p>

  <p>The generic arithmetic procedures are defined as follows:</p>

  <p><tt><a name="%_idx_2504"></a>(define&nbsp;(add&nbsp;x&nbsp;y)&nbsp;(apply-generic&nbsp;'add&nbsp;x&nbsp;y))<br />

  <a name="%_idx_2506"></a>(define&nbsp;(sub&nbsp;x&nbsp;y)&nbsp;(apply-generic&nbsp;'sub&nbsp;x&nbsp;y))<br />

  <a name="%_idx_2508"></a>(define&nbsp;(mul&nbsp;x&nbsp;y)&nbsp;(apply-generic&nbsp;'mul&nbsp;x&nbsp;y))<br />

  <a name="%_idx_2510"></a>(define&nbsp;(div&nbsp;x&nbsp;y)&nbsp;(apply-generic&nbsp;'div&nbsp;x&nbsp;y))<br />
  </tt></p>

  <p><a name="%_idx_2512"></a><a name="%_idx_2514"></a>We begin by
  installing a package for handling <em>ordinary</em> numbers, that
  is, the primitive numbers of our language. We will tag these with
  the symbol <tt>scheme-number</tt>. The arithmetic operations in
  this package are the primitive arithmetic procedures (so there is
  no need to define extra procedures to handle the untagged
  numbers). Since these operations each take two arguments, they
  are installed in the table keyed by the list <tt>(scheme-number
  scheme-number)</tt>: <a name="%_idx_2516"></a><a name="%_idx_2518"></a></p>

  <p><tt><a name="%_idx_2520"></a>(define&nbsp;(install-scheme-number-package)<br />
  &nbsp;&nbsp;(define&nbsp;(tag&nbsp;x)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;(attach-tag&nbsp;'scheme-number&nbsp;x))&nbsp;&nbsp;&nbsp;&nbsp;<br />

  &nbsp;&nbsp;(put&nbsp;'add&nbsp;'(scheme-number&nbsp;scheme-number)<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(lambda&nbsp;(x&nbsp;y)&nbsp;(tag&nbsp;(+&nbsp;x&nbsp;y))))<br />

  &nbsp;&nbsp;(put&nbsp;'sub&nbsp;'(scheme-number&nbsp;scheme-number)<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(lambda&nbsp;(x&nbsp;y)&nbsp;(tag&nbsp;(-&nbsp;x&nbsp;y))))<br />

  &nbsp;&nbsp;(put&nbsp;'mul&nbsp;'(scheme-number&nbsp;scheme-number)<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(lambda&nbsp;(x&nbsp;y)&nbsp;(tag&nbsp;(*&nbsp;x&nbsp;y))))<br />

  &nbsp;&nbsp;(put&nbsp;'div&nbsp;'(scheme-number&nbsp;scheme-number)<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(lambda&nbsp;(x&nbsp;y)&nbsp;(tag&nbsp;(/&nbsp;x&nbsp;y))))<br />

  &nbsp;&nbsp;(put&nbsp;'make&nbsp;'scheme-number<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(lambda&nbsp;(x)&nbsp;(tag&nbsp;x)))<br />

  &nbsp;&nbsp;'done)<br /></tt></p>

  <p>Users of the Scheme-number package will create (tagged)
  ordinary numbers by means of the procedure:</p>

  <p><tt><a name="%_idx_2522"></a>(define&nbsp;(make-scheme-number&nbsp;n)<br />
  &nbsp;&nbsp;((get&nbsp;'make&nbsp;'scheme-number)&nbsp;n))<br /></tt></p>

  <p>Now that the framework of the generic arithmetic system is in
  place, we can readily include new kinds of numbers. Here is a
  package that performs rational arithmetic. Notice that, as a
  benefit of additivity, we can use without modification the
  rational-number code from section&nbsp;<a href="book-Z-H-14.html#%_sec_2.1.1">2.1.1</a> as the internal
  procedures in the package: <a name="%_idx_2524"></a><a name="%_idx_2526"></a><a name="%_idx_2528"></a></p>

  <p><tt><a name="%_idx_2530"></a>(define&nbsp;(install-rational-package)<br />
  &nbsp;&nbsp;<em>;;&nbsp;internal&nbsp;procedures</em><br />
  &nbsp;&nbsp;(define&nbsp;(numer&nbsp;x)&nbsp;(car&nbsp;x))<br />
  &nbsp;&nbsp;(define&nbsp;(denom&nbsp;x)&nbsp;(cdr&nbsp;x))<br />
  &nbsp;&nbsp;(define&nbsp;(make-rat&nbsp;n&nbsp;d)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;(let&nbsp;((g&nbsp;(gcd&nbsp;n&nbsp;d)))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(cons&nbsp;(/&nbsp;n&nbsp;g)&nbsp;(/&nbsp;d&nbsp;g))))<br />

  &nbsp;&nbsp;(define&nbsp;(add-rat&nbsp;x&nbsp;y)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;(make-rat&nbsp;(+&nbsp;(*&nbsp;(numer&nbsp;x)&nbsp;(denom&nbsp;y))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;(numer&nbsp;y)&nbsp;(denom&nbsp;x)))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;(denom&nbsp;x)&nbsp;(denom&nbsp;y))))<br />

  &nbsp;&nbsp;(define&nbsp;(sub-rat&nbsp;x&nbsp;y)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;(make-rat&nbsp;(-&nbsp;(*&nbsp;(numer&nbsp;x)&nbsp;(denom&nbsp;y))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;(numer&nbsp;y)&nbsp;(denom&nbsp;x)))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;(denom&nbsp;x)&nbsp;(denom&nbsp;y))))<br />

  &nbsp;&nbsp;(define&nbsp;(mul-rat&nbsp;x&nbsp;y)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;(make-rat&nbsp;(*&nbsp;(numer&nbsp;x)&nbsp;(numer&nbsp;y))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;(denom&nbsp;x)&nbsp;(denom&nbsp;y))))<br />

  &nbsp;&nbsp;(define&nbsp;(div-rat&nbsp;x&nbsp;y)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;(make-rat&nbsp;(*&nbsp;(numer&nbsp;x)&nbsp;(denom&nbsp;y))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;(denom&nbsp;x)&nbsp;(numer&nbsp;y))))<br />

  &nbsp;&nbsp;<em>;;&nbsp;interface&nbsp;to&nbsp;rest&nbsp;of&nbsp;the&nbsp;system</em><br />

  &nbsp;&nbsp;(define&nbsp;(tag&nbsp;x)&nbsp;(attach-tag&nbsp;'rational&nbsp;x))<br />

  &nbsp;&nbsp;(put&nbsp;'add&nbsp;'(rational&nbsp;rational)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(lambda&nbsp;(x&nbsp;y)&nbsp;(tag&nbsp;(add-rat&nbsp;x&nbsp;y))))<br />

  &nbsp;&nbsp;(put&nbsp;'sub&nbsp;'(rational&nbsp;rational)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(lambda&nbsp;(x&nbsp;y)&nbsp;(tag&nbsp;(sub-rat&nbsp;x&nbsp;y))))<br />

  &nbsp;&nbsp;(put&nbsp;'mul&nbsp;'(rational&nbsp;rational)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(lambda&nbsp;(x&nbsp;y)&nbsp;(tag&nbsp;(mul-rat&nbsp;x&nbsp;y))))<br />

  &nbsp;&nbsp;(put&nbsp;'div&nbsp;'(rational&nbsp;rational)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(lambda&nbsp;(x&nbsp;y)&nbsp;(tag&nbsp;(div-rat&nbsp;x&nbsp;y))))<br />

  <br />
  &nbsp;&nbsp;(put&nbsp;'make&nbsp;'rational<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(lambda&nbsp;(n&nbsp;d)&nbsp;(tag&nbsp;(make-rat&nbsp;n&nbsp;d))))<br />

  &nbsp;&nbsp;'done)<br />
  <a name="%_idx_2532"></a>(define&nbsp;(make-rational&nbsp;n&nbsp;d)<br />
  &nbsp;&nbsp;((get&nbsp;'make&nbsp;'rational)&nbsp;n&nbsp;d))<br /></tt></p>

  <p>We can install a similar package to handle complex numbers,
  using the tag <tt>complex</tt>. In creating the package, we
  extract from the table the operations
  <tt>make-from-real-imag</tt> and <tt>make-from-mag-ang</tt> that
  were defined by the rectangular and polar packages. <a name="%_idx_2534"></a>Additivity permits us to use, as the internal
  operations, the same <tt>add-complex</tt>, <tt>sub-complex</tt>,
  <tt>mul-complex</tt>, and <tt>div-complex</tt> procedures from
  section&nbsp;<a href="book-Z-H-17.html#%_sec_2.4.1">2.4.1</a>.
  <a name="%_idx_2536"></a><a name="%_idx_2538"></a><a name="%_idx_2540"></a></p>

  <p><tt><a name="%_idx_2542"></a>(define&nbsp;(install-complex-package)<br />
  &nbsp;&nbsp;<em>;;&nbsp;imported&nbsp;procedures&nbsp;from&nbsp;rectangular&nbsp;and&nbsp;polar&nbsp;packages</em><br />

  &nbsp;&nbsp;(define&nbsp;(make-from-real-imag&nbsp;x&nbsp;y)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;((get&nbsp;'make-from-real-imag&nbsp;'rectangular)&nbsp;x&nbsp;y))<br />

  &nbsp;&nbsp;(define&nbsp;(make-from-mag-ang&nbsp;r&nbsp;a)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;((get&nbsp;'make-from-mag-ang&nbsp;'polar)&nbsp;r&nbsp;a))<br />

  &nbsp;&nbsp;<em>;;&nbsp;internal&nbsp;procedures</em><br />
  &nbsp;&nbsp;(define&nbsp;(add-complex&nbsp;z1&nbsp;z2)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;(make-from-real-imag&nbsp;(+&nbsp;(real-part&nbsp;z1)&nbsp;(real-part&nbsp;z2))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(+&nbsp;(imag-part&nbsp;z1)&nbsp;(imag-part&nbsp;z2))))<br />

  &nbsp;&nbsp;(define&nbsp;(sub-complex&nbsp;z1&nbsp;z2)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;(make-from-real-imag&nbsp;(-&nbsp;(real-part&nbsp;z1)&nbsp;(real-part&nbsp;z2))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(-&nbsp;(imag-part&nbsp;z1)&nbsp;(imag-part&nbsp;z2))))<br />

  &nbsp;&nbsp;(define&nbsp;(mul-complex&nbsp;z1&nbsp;z2)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;(make-from-mag-ang&nbsp;(*&nbsp;(magnitude&nbsp;z1)&nbsp;(magnitude&nbsp;z2))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(+&nbsp;(angle&nbsp;z1)&nbsp;(angle&nbsp;z2))))<br />

  &nbsp;&nbsp;(define&nbsp;(div-complex&nbsp;z1&nbsp;z2)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;(make-from-mag-ang&nbsp;(/&nbsp;(magnitude&nbsp;z1)&nbsp;(magnitude&nbsp;z2))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(-&nbsp;(angle&nbsp;z1)&nbsp;(angle&nbsp;z2))))<br />

  &nbsp;&nbsp;<em>;;&nbsp;interface&nbsp;to&nbsp;rest&nbsp;of&nbsp;the&nbsp;system</em><br />

  &nbsp;&nbsp;(define&nbsp;(tag&nbsp;z)&nbsp;(attach-tag&nbsp;'complex&nbsp;z))<br />

  &nbsp;&nbsp;(put&nbsp;'add&nbsp;'(complex&nbsp;complex)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(lambda&nbsp;(z1&nbsp;z2)&nbsp;(tag&nbsp;(add-complex&nbsp;z1&nbsp;z2))))<br />

  &nbsp;&nbsp;(put&nbsp;'sub&nbsp;'(complex&nbsp;complex)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(lambda&nbsp;(z1&nbsp;z2)&nbsp;(tag&nbsp;(sub-complex&nbsp;z1&nbsp;z2))))<br />

  &nbsp;&nbsp;(put&nbsp;'mul&nbsp;'(complex&nbsp;complex)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(lambda&nbsp;(z1&nbsp;z2)&nbsp;(tag&nbsp;(mul-complex&nbsp;z1&nbsp;z2))))<br />

  &nbsp;&nbsp;(put&nbsp;'div&nbsp;'(complex&nbsp;complex)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(lambda&nbsp;(z1&nbsp;z2)&nbsp;(tag&nbsp;(div-complex&nbsp;z1&nbsp;z2))))<br />

  &nbsp;&nbsp;(put&nbsp;'make-from-real-imag&nbsp;'complex<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(lambda&nbsp;(x&nbsp;y)&nbsp;(tag&nbsp;(make-from-real-imag&nbsp;x&nbsp;y))))<br />

  &nbsp;&nbsp;(put&nbsp;'make-from-mag-ang&nbsp;'complex<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(lambda&nbsp;(r&nbsp;a)&nbsp;(tag&nbsp;(make-from-mag-ang&nbsp;r&nbsp;a))))<br />

  &nbsp;&nbsp;'done)<br /></tt></p>

  <p>Programs outside the complex-number package can construct
  complex numbers either from real and imaginary parts or from
  magnitudes and angles. Notice how the underlying procedures,
  originally defined in the rectangular and polar packages, are
  exported to the complex package, and exported from there to the
  outside world.</p>

  <p><tt><a name="%_idx_2544"></a>(define&nbsp;(make-complex-from-real-imag&nbsp;x&nbsp;y)<br />

  &nbsp;&nbsp;((get&nbsp;'make-from-real-imag&nbsp;'complex)&nbsp;x&nbsp;y))<br />

  <a name="%_idx_2546"></a>(define&nbsp;(make-complex-from-mag-ang&nbsp;r&nbsp;a)<br />

  &nbsp;&nbsp;((get&nbsp;'make-from-mag-ang&nbsp;'complex)&nbsp;r&nbsp;a))<br />
  </tt></p>

  <p><a name="%_idx_2548"></a>What we have here is a two-level tag
  system. A typical complex number, such as 3 + 4<em>i</em> in
  rectangular form, would be represented as shown in
  figure&nbsp;<a href="#%_fig_2.24">2.24</a>. The outer tag
  (<tt>complex</tt>) is used to direct the number to the complex
  package. Once within the complex package, the next tag
  (<tt>rectangular</tt>) is used to direct the number to the
  rectangular package. In a large and complicated system there
  might be many levels, each interfaced with the next by means of
  generic operations. As a data object is passed ``downward,'' the
  outer tag that is used to direct it to the appropriate package is
  stripped off (by applying <tt>contents</tt>) and the next level
  of tag (if any) becomes visible to be used for further
  dispatching.</p>

  <p><a name="%_fig_2.24"></a></p>

  <div align="left">
    <div align="left">
      <b>Figure 2.24:</b>&nbsp;&nbsp;Representation of 3 +
      4<em>i</em> in rectangular form.
    </div>

    <table width="100%">
      <tr>
        <td><img src="ch2-Z-G-65.gif" border="0" /></td>
      </tr>

      <tr>
        <td></td>
      </tr>
    </table>
  </div>

  <p>In the above packages, we used <tt>add-rat</tt>,
  <tt>add-complex</tt>, and the other arithmetic procedures exactly
  as originally written. Once these definitions are internal to
  different installation procedures, however, they no longer need
  names that are distinct from each other: we could simply name
  them <tt>add</tt>, <tt>sub</tt>, <tt>mul</tt>, and <tt>div</tt>
  in both packages.</p>

  <p><a name="%_thm_2.77"></a> <b>Exercise
  2.77.</b>&nbsp;&nbsp;Louis Reasoner tries to evaluate the
  expression <tt>(magnitude z)</tt> where <tt>z</tt> is the object
  shown in figure&nbsp;<a href="#%_fig_2.24">2.24</a>. To his
  surprise, instead of the answer 5 he gets an error message from
  <tt>apply-generic</tt>, saying there is no method for the
  operation <tt>magnitude</tt> on the types <tt>(complex)</tt>. He
  shows this interaction to Alyssa P. Hacker, who says ``The
  problem is that the complex-number selectors were never defined
  for <tt>complex</tt> numbers, just for <tt>polar</tt> and
  <tt>rectangular</tt> numbers. All you have to do to make this
  work is add the following to the <tt>complex</tt> package:''</p>

  <p><tt>(put&nbsp;'real-part&nbsp;'(complex)&nbsp;real-part)<br />
  (put&nbsp;'imag-part&nbsp;'(complex)&nbsp;imag-part)<br />
  (put&nbsp;'magnitude&nbsp;'(complex)&nbsp;magnitude)<br />
  (put&nbsp;'angle&nbsp;'(complex)&nbsp;angle)<br /></tt></p>

  <p>Describe in detail why this works. As an example, trace
  through all the procedures called in evaluating the expression
  <tt>(magnitude z)</tt> where <tt>z</tt> is the object shown in
  figure&nbsp;<a href="#%_fig_2.24">2.24</a>. In particular, how
  many times is <tt>apply-generic</tt> invoked? What procedure is
  dispatched to in each case?</p>

  <p><a name="%_thm_2.78"></a> <b>Exercise
  2.78.</b>&nbsp;&nbsp;<a name="%_idx_2550"></a><a name="%_idx_2552"></a><a name="%_idx_2554"></a><a name="%_idx_2556"></a><a name="%_idx_2558"></a><a name="%_idx_2560"></a><a name="%_idx_2562"></a>The internal procedures
  in the <tt>scheme-number</tt> package are essentially nothing
  more than calls to the primitive procedures <tt>+</tt>,
  <tt>-</tt>, etc. It was not possible to use the primitives of the
  language directly because our type-tag system requires that each
  data object have a type attached to it. In fact, however, all
  Lisp implementations do have a type system, which they use
  internally. Primitive predicates such as <tt>symbol?</tt> and
  <tt>number?</tt> determine whether data objects have particular
  types. Modify the definitions of <tt>type-tag</tt>,
  <tt>contents</tt>, and <tt>attach-tag</tt> from
  section&nbsp;<a href="book-Z-H-17.html#%_sec_2.4.2">2.4.2</a> so
  that our generic system takes advantage of Scheme's internal type
  system. That is to say, the system should work as before except
  that ordinary numbers should be represented simply as Scheme
  numbers rather than as pairs whose <tt>car</tt> is the symbol
  <tt>scheme-number</tt>.</p>

  <p><a name="%_thm_2.79"></a> <b>Exercise
  2.79.</b>&nbsp;&nbsp;<a name="%_idx_2564"></a><a name="%_idx_2566"></a>Define a generic equality predicate
  <tt>equ?</tt> that tests the equality of two numbers, and install
  it in the generic arithmetic package. This operation should work
  for ordinary numbers, rational numbers, and complex numbers.</p>

  <p><a name="%_thm_2.80"></a> <b>Exercise
  2.80.</b>&nbsp;&nbsp;<a name="%_idx_2568"></a><a name="%_idx_2570"></a>Define a generic predicate <tt>=zero?</tt> that
  tests if its argument is zero, and install it in the generic
  arithmetic package. This operation should work for ordinary
  numbers, rational numbers, and complex numbers.</p>

  <p><a name="%_sec_2.5.2"></a></p>

  <h3><a href="book-Z-H-4.html#%_toc_%_sec_2.5.2">2.5.2&nbsp;&nbsp;Combining
  Data of Different Types</a></h3>

  <p>We have seen how to define a unified arithmetic system that
  encompasses ordinary numbers, complex numbers, rational numbers,
  and any other type of number we might decide to invent, but we
  have ignored an important issue. The operations we have defined
  so far treat the different data types as being completely
  independent. Thus, there are separate packages for adding, say,
  two ordinary numbers, or two complex numbers. What we have not
  yet considered is the fact that it is meaningful to define
  operations that cross the type boundaries, such as the addition
  of a complex number to an ordinary number. We have gone to great
  pains to introduce barriers between parts of our programs so that
  they can be developed and understood separately. We would like to
  introduce the cross-type operations in some carefully controlled
  way, so that we can support them without seriously violating our
  module boundaries.</p>

  <p><a name="%_idx_2572"></a><a name="%_idx_2574"></a><a name="%_idx_2576"></a>One way to handle cross-type operations is to
  design a different procedure for each possible combination of
  types for which the operation is valid. For example, we could
  extend the complex-number package so that it provides a procedure
  for adding complex numbers to ordinary numbers and installs this
  in the table using the tag <tt>(complex
  scheme-number)</tt>:<a href="#footnote_Temp_283" name="call_footnote_Temp_283" id="call_footnote_Temp_283"><sup><small>49</small></sup></a></p>

  <p>
  <tt><em>;;&nbsp;to&nbsp;be&nbsp;included&nbsp;in&nbsp;the&nbsp;complex&nbsp;package</em><br />

  <a name="%_idx_2578"></a>(define&nbsp;(add-complex-to-schemenum&nbsp;z&nbsp;x)<br />

  &nbsp;&nbsp;(make-from-real-imag&nbsp;(+&nbsp;(real-part&nbsp;z)&nbsp;x)<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(imag-part&nbsp;z)))<br />

  (put&nbsp;'add&nbsp;'(complex&nbsp;scheme-number)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(lambda&nbsp;(z&nbsp;x)&nbsp;(tag&nbsp;(add-complex-to-schemenum&nbsp;z&nbsp;x))))<br />
  </tt></p>

  <p>This technique works, but it is cumbersome. With such a
  system, the cost of introducing a new type is not just the
  construction of the package of procedures for that type but also
  the construction and installation of the procedures that
  implement the cross-type operations. This can easily be much more
  code than is needed to define the operations on the type itself.
  The method also undermines our ability to combine separate
  packages additively, or least to limit the extent to which the
  implementors of the individual packages need to take account of
  other packages. For instance, in the example above, it seems
  reasonable that handling mixed operations on complex numbers and
  ordinary numbers should be the responsibility of the
  complex-number package. Combining rational numbers and complex
  numbers, however, might be done by the complex package, by the
  rational package, or by some third package that uses operations
  extracted from these two packages. Formulating coherent policies
  on the division of responsibility among packages can be an
  overwhelming task in designing systems with many packages and
  many cross-type operations.</p>

  <p><a name="%_sec_Temp_284"></a></p>

  <h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_284">Coercion</a></h4>

  <p><a name="%_idx_2580"></a> In the general situation of
  completely unrelated operations acting on completely unrelated
  types, implementing explicit cross-type operations, cumbersome
  though it may be, is the best that one can hope for. Fortunately,
  we can usually do better by taking advantage of additional
  structure that may be latent in our type system. Often the
  different data types are not completely independent, and there
  may be ways by which objects of one type may be viewed as being
  of another type. This process is called <em>coercion</em>. For
  example, if we are asked to arithmetically combine an ordinary
  number with a complex number, we can view the ordinary number as
  a complex number whose imaginary part is zero. This transforms
  the problem to that of combining two complex numbers, which can
  be handled in the ordinary way by the complex-arithmetic
  package.</p>

  <p><a name="%_idx_2582"></a>In general, we can implement this
  idea by designing coercion procedures that transform an object of
  one type into an equivalent object of another type. Here is a
  typical coercion procedure, which transforms a given ordinary
  number to a complex number with that real part and zero imaginary
  part:</p>

  <p><tt><a name="%_idx_2584"></a>(define&nbsp;(scheme-number-&gt;complex&nbsp;n)<br />

  &nbsp;&nbsp;(make-complex-from-real-imag&nbsp;(contents&nbsp;n)&nbsp;0))<br />
  </tt></p>

  <p><a name="%_idx_2586"></a><a name="%_idx_2588"></a>We install
  these coercion procedures in a special coercion table, indexed
  under the names of the two types:</p>

  <p>
  <tt>(put-coercion&nbsp;'scheme-number&nbsp;'complex&nbsp;scheme-number-&gt;complex)<br />
  </tt></p>

  <p>(We assume that there are <tt>put-coercion</tt> and
  <tt>get-coercion</tt> procedures available for manipulating this
  table.) Generally some of the slots in the table will be empty,
  because it is not generally possible to coerce an arbitrary data
  object of each type into all other types. For example, there is
  no way to coerce an arbitrary complex number to an ordinary
  number, so there will be no general
  <tt>complex-&gt;scheme-number</tt> procedure included in the
  table.</p>

  <p>Once the coercion table has been set up, we can handle
  coercion in a uniform manner by modifying the
  <tt>apply-generic</tt> procedure of section&nbsp;<a href="book-Z-H-17.html#%_sec_2.4.3">2.4.3</a>. When asked to apply an
  operation, we first check whether the operation is defined for
  the arguments' types, just as before. If so, we dispatch to the
  procedure found in the operation-and-type table. Otherwise, we
  try coercion. For simplicity, we consider only the case where
  there are two arguments.<a href="#footnote_Temp_285" name="call_footnote_Temp_285" id="call_footnote_Temp_285"><sup><small>50</small></sup></a> We
  check the coercion table to see if objects of the first type can
  be coerced to the second type. If so, we coerce the first
  argument and try the operation again. If objects of the first
  type cannot in general be coerced to the second type, we try the
  coercion the other way around to see if there is a way to coerce
  the second argument to the type of the first argument. Finally,
  if there is no known way to coerce either type to the other type,
  we give up. Here is the procedure:</p>

  <p><tt><a name="%_idx_2590"></a>(define&nbsp;(apply-generic&nbsp;op&nbsp;.&nbsp;args)<br />

  &nbsp;&nbsp;(let&nbsp;((type-tags&nbsp;(map&nbsp;type-tag&nbsp;args)))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;(let&nbsp;((proc&nbsp;(get&nbsp;op&nbsp;type-tags)))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(if&nbsp;proc<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(apply&nbsp;proc&nbsp;(map&nbsp;contents&nbsp;args))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(if&nbsp;(=&nbsp;(length&nbsp;args)&nbsp;2)<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(let&nbsp;((type1&nbsp;(car&nbsp;type-tags))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(type2&nbsp;(cadr&nbsp;type-tags))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(a1&nbsp;(car&nbsp;args))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(a2&nbsp;(cadr&nbsp;args)))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(let&nbsp;((t1-&gt;t2&nbsp;(get-coercion&nbsp;type1&nbsp;type2))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(t2-&gt;t1&nbsp;(get-coercion&nbsp;type2&nbsp;type1)))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(cond&nbsp;(t1-&gt;t2<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(apply-generic&nbsp;op&nbsp;(t1-&gt;t2&nbsp;a1)&nbsp;a2))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(t2-&gt;t1<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(apply-generic&nbsp;op&nbsp;a1&nbsp;(t2-&gt;t1&nbsp;a2)))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(error&nbsp;"No&nbsp;method&nbsp;for&nbsp;these&nbsp;types"<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(list&nbsp;op&nbsp;type-tags))))))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(error&nbsp;"No&nbsp;method&nbsp;for&nbsp;these&nbsp;types"<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(list&nbsp;op&nbsp;type-tags)))))))<br />
  </tt></p>

  <p>This coercion scheme has many advantages over the method of
  defining explicit cross-type operations, as outlined above.
  Although we still need to write coercion procedures to relate the
  types (possibly <em>n</em><sup>2</sup> procedures for a system
  with <em>n</em> types), we need to write only one procedure for
  each pair of types rather than a different procedure for each
  collection of types and each generic operation.<a href="#footnote_Temp_286" name="call_footnote_Temp_286" id="call_footnote_Temp_286"><sup><small>51</small></sup></a> What we
  are counting on here is the fact that the appropriate
  transformation between types depends only on the types
  themselves, not on the operation to be applied.</p>

  <p>On the other hand, there may be applications for which our
  coercion scheme is not general enough. Even when neither of the
  objects to be combined can be converted to the type of the other
  it may still be possible to perform the operation by converting
  both objects to a third type. In order to deal with such
  complexity and still preserve modularity in our programs, it is
  usually necessary to build systems that take advantage of still
  further structure in the relations among types, as we discuss
  next.</p>

  <p><a name="%_sec_Temp_287"></a></p>

  <h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_287">Hierarchies of
  types</a></h4>

  <p><a name="%_idx_2592"></a><a name="%_idx_2594"></a> The
  coercion scheme presented above relied on the existence of
  natural relations between pairs of types. Often there is more
  ``global'' structure in how the different types relate to each
  other. For instance, suppose we are building a generic arithmetic
  system to handle integers, rational numbers, real numbers, and
  complex numbers. In such a system, it is quite natural to regard
  an integer as a special kind of rational number, which is in turn
  a special kind of real number, which is in turn a special kind of
  complex number. What we actually have is a so-called
  <em>hierarchy of types</em>, in which, for example, integers are
  a <a name="%_idx_2596"></a><a name="%_idx_2598"></a><em>subtype</em> of rational numbers (i.e., any
  operation that can be applied to a rational number can
  automatically be applied to an integer). Conversely, we say that
  rational numbers form a <a name="%_idx_2600"></a><a name="%_idx_2602"></a><em>supertype</em> of integers. The particular
  hierarchy we have here is of a very simple kind, in which each
  type has at most one supertype and at most one subtype. Such a
  structure, called a <em>tower</em>, is illustrated in
  figure&nbsp;<a href="#%_fig_2.25">2.25</a>.</p>

  <p><a name="%_fig_2.25"></a></p>

  <div align="left">
    <div align="left">
      <b>Figure 2.25:</b>&nbsp;&nbsp;A tower of types.
    </div>

    <table width="100%">
      <tr>
        <td><img src="ch2-Z-G-66.gif" border="0" /></td>
      </tr>

      <tr>
        <td><a name="%_idx_2604"></a><a name="%_idx_2606"></a></td>
      </tr>
    </table>
  </div>

  <p>If we have a tower structure, then we can greatly simplify the
  problem of adding a new type to the hierarchy, for we need only
  specify how the new type is embedded in the next supertype above
  it and how it is the supertype of the type below it. For example,
  if we want to add an integer to a complex number, we need not
  explicitly define a special coercion procedure
  <tt>integer-&gt;complex</tt>. Instead, we define how an integer
  can be transformed into a rational number, how a rational number
  is transformed into a real number, and how a real number is
  transformed into a complex number. We then allow the system to
  transform the integer into a complex number through these steps
  and then add the two complex numbers.</p>

  <p><a name="%_idx_2608"></a><a name="%_idx_2610"></a>We can
  redesign our <tt>apply-generic</tt> procedure in the following
  way: For each type, we need to supply a <tt>raise</tt> procedure,
  which ``raises'' objects of that type one level in the tower.
  Then when the system is required to operate on objects of
  different types it can successively raise the lower types until
  all the objects are at the same level in the tower.
  (Exercises&nbsp;<a href="#%_thm_2.83">2.83</a> and &nbsp;<a href="#%_thm_2.84">2.84</a> concern the details of implementing such a
  strategy.)</p>

  <p>Another advantage of a tower is that we can easily implement
  the notion that every type ``inherits'' all operations defined on
  a supertype. For instance, if we do not supply a special
  procedure for finding the real part of an integer, we should
  nevertheless expect that <tt>real-part</tt> will be defined for
  integers by virtue of the fact that integers are a subtype of
  complex numbers. In a tower, we can arrange for this to happen in
  a uniform way by modifying <tt>apply-generic</tt>. If the
  required operation is not directly defined for the type of the
  object given, we raise the object to its supertype and try again.
  We thus crawl up the tower, transforming our argument as we go,
  until we either find a level at which the desired operation can
  be performed or hit the top (in which case we give up).</p>

  <p><a name="%_idx_2612"></a>Yet another advantage of a tower over
  a more general hierarchy is that it gives us a simple way to
  ``lower'' a data object to the simplest representation. For
  example, if we add 2 + 3<em>i</em> to 4 - 3<em>i</em>, it would
  be nice to obtain the answer as the integer 6 rather than as the
  complex number 6 + 0<em>i</em>. Exercise&nbsp;<a href="#%_thm_2.85">2.85</a> discusses a way to implement such a
  lowering operation. (The trick is that we need a general way to
  distinguish those objects that can be lowered, such as 6 +
  0<em>i</em>, from those that cannot, such as 6 +
  2<em>i</em>.)</p>

  <p><a name="%_fig_2.26"></a></p>

  <div align="left">
    <div align="left">
      <b>Figure 2.26:</b>&nbsp;&nbsp;Relations among types of
      geometric figures.
    </div>

    <table width="100%">
      <tr>
        <td><img src="ch2-Z-G-67.gif" border="0" /></td>
      </tr>

      <tr>
        <td></td>
      </tr>
    </table>
  </div>

  <p><a name="%_sec_Temp_288"></a></p>

  <h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_288">Inadequacies
  of hierarchies</a></h4>

  <p><a name="%_idx_2614"></a> If the data types in our system can
  be naturally arranged in a tower, this greatly simplifies the
  problems of dealing with generic operations on different types,
  as we have seen. Unfortunately, this is usually not the case.
  Figure&nbsp;<a href="#%_fig_2.26">2.26</a> illustrates a more
  complex arrangement of mixed types, this one showing relations
  among different types of geometric figures. We see that, in
  general, <a name="%_idx_2616"></a><a name="%_idx_2618"></a><a name="%_idx_2620"></a>a type may have more
  than one subtype. Triangles and quadrilaterals, for instance, are
  both subtypes of polygons. In addition, a type may have more than
  one supertype. For example, an isosceles right triangle may be
  regarded either as an isosceles triangle or as a right triangle.
  This multiple-supertypes issue is particularly thorny, since it
  means that there is no unique way to ``raise'' a type in the
  hierarchy. Finding the ``correct'' supertype in which to apply an
  operation to an object may involve considerable searching through
  the entire type network on the part of a procedure such as
  <tt>apply-generic</tt>. Since there generally are multiple
  subtypes for a type, there is a similar problem in coercing a
  value ``down'' the type hierarchy. Dealing with large numbers of
  interrelated types while still preserving modularity in the
  design of large systems is very difficult, and is an area of much
  current research.<a href="#footnote_Temp_289" name="call_footnote_Temp_289" id="call_footnote_Temp_289"><sup><small>52</small></sup></a></p>

  <p><a name="%_thm_2.81"></a> <b>Exercise
  2.81.</b>&nbsp;&nbsp;<a name="%_idx_2626"></a>Louis Reasoner has
  noticed that <tt>apply-generic</tt> may try to coerce the
  arguments to each other's type even if they already have the same
  type. Therefore, he reasons, we need to put procedures in the
  coercion table to "coerce" arguments of each type to their own
  type. For example, in addition to the
  <tt>scheme-number-&gt;complex</tt> coercion shown above, he would
  do:</p>

  <p><tt><a name="%_idx_2628"></a>(define&nbsp;(scheme-number-&gt;scheme-number&nbsp;n)&nbsp;n)<br />

  <a name="%_idx_2630"></a>(define&nbsp;(complex-&gt;complex&nbsp;z)&nbsp;z)<br />

  (put-coercion&nbsp;'scheme-number&nbsp;'scheme-number<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scheme-number-&gt;scheme-number)<br />

  (put-coercion&nbsp;'complex&nbsp;'complex&nbsp;complex-&gt;complex)<br />
  </tt></p>

  <p>a. With Louis's coercion procedures installed, what happens if
  <tt>apply-generic</tt> is called with two arguments of type
  <tt>scheme-number</tt> or two arguments of type <tt>complex</tt>
  for an operation that is not found in the table for those types?
  For example, assume that we've defined a generic exponentiation
  operation:</p>

  <p>
  <tt>(define&nbsp;(exp&nbsp;x&nbsp;y)&nbsp;(apply-generic&nbsp;'exp&nbsp;x&nbsp;y))<br />
  </tt></p>

  <p>and have put a procedure for exponentiation in the
  Scheme-number package but not in any other package:</p>

  <p>
  <tt><em>;;&nbsp;following&nbsp;added&nbsp;to&nbsp;Scheme-number&nbsp;package</em><br />

  (put&nbsp;'exp&nbsp;'(scheme-number&nbsp;scheme-number)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(lambda&nbsp;(x&nbsp;y)&nbsp;(tag&nbsp;(expt&nbsp;x&nbsp;y))))&nbsp;<em>;&nbsp;using&nbsp;primitive&nbsp;<tt>expt</tt></em><br />
  </tt></p>

  <p>What happens if we call <tt>exp</tt> with two complex numbers
  as arguments?</p>

  <p>b. Is Louis correct that something had to be done about
  coercion with arguments of the same type, or does
  <tt>apply-generic</tt> work correctly as is?</p>

  <p>c. Modify <tt>apply-generic</tt> so that it doesn't try
  coercion if the two arguments have the same type.</p>

  <p><a name="%_thm_2.82"></a> <b>Exercise
  2.82.</b>&nbsp;&nbsp;<a name="%_idx_2632"></a>Show how to
  generalize <tt>apply-generic</tt> to handle coercion in the
  general case of multiple arguments. One strategy is to attempt to
  coerce all the arguments to the type of the first argument, then
  to the type of the second argument, and so on. Give an example of
  a situation where this strategy (and likewise the two-argument
  version given above) is not sufficiently general. (Hint: Consider
  the case where there are some suitable mixed-type operations
  present in the table that will not be tried.)</p>

  <p><a name="%_thm_2.83"></a> <b>Exercise
  2.83.</b>&nbsp;&nbsp;<a name="%_idx_2634"></a>Suppose you are
  designing a generic arithmetic system for dealing with the tower
  of types shown in figure&nbsp;<a href="#%_fig_2.25">2.25</a>:
  integer, rational, real, complex. For each type (except complex),
  design a procedure that raises objects of that type one level in
  the tower. Show how to install a generic <tt>raise</tt> operation
  that will work for each type (except complex).</p>

  <p><a name="%_thm_2.84"></a> <b>Exercise
  2.84.</b>&nbsp;&nbsp;<a name="%_idx_2636"></a>Using the
  <tt>raise</tt> operation of exercise&nbsp;<a href="#%_thm_2.83">2.83</a>, modify the <tt>apply-generic</tt>
  procedure so that it coerces its arguments to have the same type
  by the method of successive raising, as discussed in this
  section. You will need to devise a way to test which of two types
  is higher in the tower. Do this in a manner that is
  ``compatible'' with the rest of the system and will not lead to
  problems in adding new levels to the tower.</p>

  <p><a name="%_thm_2.85"></a> <b>Exercise
  2.85.</b>&nbsp;&nbsp;<a name="%_idx_2638"></a><a name="%_idx_2640"></a>This section mentioned a method for
  ``simplifying'' a data object by lowering it in the tower of
  types as far as possible. Design a procedure <tt>drop</tt> that
  accomplishes this for the tower described in
  exercise&nbsp;<a href="#%_thm_2.83">2.83</a>. The key is to
  decide, in some general way, whether an object can be lowered.
  For example, the complex number 1.5 + 0<em>i</em> can be lowered
  as far as <tt>real</tt>, the complex number 1 + 0<em>i</em> can
  be lowered as far as <tt>integer</tt>, and the complex number 2 +
  3<em>i</em> cannot be lowered at all. Here is a plan for
  determining whether an object can be lowered: Begin by defining a
  generic operation <tt>project</tt> that ``pushes'' an object down
  in the tower. For example, projecting a complex number would
  involve throwing away the imaginary part. Then a number can be
  dropped if, when we <tt>project</tt> it and <tt>raise</tt> the
  result back to the type we started with, we end up with something
  equal to what we started with. Show how to implement this idea in
  detail, by writing a <tt>drop</tt> procedure that drops an object
  as far as possible. You will need to design the various
  projection operations<a href="#footnote_Temp_295" name="call_footnote_Temp_295" id="call_footnote_Temp_295"><sup><small>53</small></sup></a> and
  install <tt>project</tt> as a generic operation in the system.
  You will also need to make use of a generic equality predicate,
  such as described in exercise&nbsp;<a href="#%_thm_2.79">2.79</a>. Finally, use <tt>drop</tt> to rewrite
  <tt>apply-generic</tt> from exercise&nbsp;<a href="#%_thm_2.84">2.84</a> so that it ``simplifies'' its answers.</p>

  <p><a name="%_thm_2.86"></a> <b>Exercise
  2.86.</b>&nbsp;&nbsp;Suppose we want to handle complex numbers
  whose real parts, imaginary parts, magnitudes, and angles can be
  either ordinary numbers, rational numbers, or other numbers we
  might wish to add to the system. Describe and implement the
  changes to the system needed to accommodate this. You will have
  to define operations such as <tt>sine</tt> and <tt>cosine</tt>
  that are generic over ordinary numbers and rational numbers.</p>

  <p><a name="%_sec_2.5.3"></a></p>

  <h3><a href="book-Z-H-4.html#%_toc_%_sec_2.5.3">2.5.3&nbsp;&nbsp;Example:
  Symbolic Algebra</a></h3>

  <p><a name="%_idx_2646"></a> 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 <a name="%_idx_2648"></a>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</p>

  <div align="left"><img src="ch2-Z-G-68.gif" border="0" /></div>

  <p>as a polynomial in <em>x</em> with coefficients that are
  trigonometric functions of polynomials in <em>y</em> whose
  coefficients are integers.</p>

  <p>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.</p>

  <p><a name="%_sec_Temp_297"></a></p>

  <h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_297">Arithmetic on
  polynomials</a></h4>

  <p><a name="%_idx_2650"></a><a name="%_idx_2652"></a> 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 <a name="%_idx_2654"></a><a name="%_idx_2656"></a><em>indeterminates</em>
  of the polynomial). For simplicity, we will restrict ourselves to
  polynomials having just one indeterminate (<a name="%_idx_2658"></a><a name="%_idx_2660"></a><em>univariate
  polynomials</em>).<a href="#footnote_Temp_298" name="call_footnote_Temp_298" id="call_footnote_Temp_298"><sup><small>54</small></sup></a> 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,</p>

  <div align="left"><img src="ch2-Z-G-69.gif" border="0" /></div>

  <p>is a simple polynomial in <em>x</em>, and</p>

  <div align="left"><img src="ch2-Z-G-70.gif" border="0" /></div>

  <p>is a polynomial in <em>x</em> whose coefficients are
  polynomials in <em>y</em>.</p>

  <p>Already we are skirting some thorny issues. Is the first of
  these polynomials the same as the polynomial
  5<em>y</em><sup>2</sup> + 3<em>y</em> + 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 <em>y</em> whose
  coefficients are polynomials in <em>x</em>. 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.<a href="#footnote_Temp_299" name="call_footnote_Temp_299" id="call_footnote_Temp_299"><sup><small>55</small></sup></a> 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.</p>

  <p>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.</p>

  <p>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 <a name="%_idx_2664"></a><em>poly</em>, which consists of a variable and
  a <a name="%_idx_2666"></a>collection of terms. We assume that we
  have selectors <tt>variable</tt> and <tt>term-list</tt> that
  extract those parts from a poly and a constructor
  <tt>make-poly</tt> that assembles a poly from a given variable
  and a term list. A variable will be just a symbol, so we can use
  the <a name="%_idx_2668"></a><tt>same-variable?</tt> procedure of
  section&nbsp;<a href="book-Z-H-16.html#%_sec_2.3.2">2.3.2</a> to
  compare variables. <a name="%_idx_2670"></a><a name="%_idx_2672"></a>The following procedures define addition and
  multiplication of polys:</p>

  <p><tt><a name="%_idx_2674"></a>(define&nbsp;(add-poly&nbsp;p1&nbsp;p2)<br />
  &nbsp;&nbsp;(if&nbsp;(same-variable?&nbsp;(variable&nbsp;p1)&nbsp;(variable&nbsp;p2))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(make-poly&nbsp;(variable&nbsp;p1)<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(add-terms&nbsp;(term-list&nbsp;p1)<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(term-list&nbsp;p2)))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(error&nbsp;"Polys&nbsp;not&nbsp;in&nbsp;same&nbsp;var&nbsp;--&nbsp;ADD-POLY"<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(list&nbsp;p1&nbsp;p2))))<br />

  <a name="%_idx_2676"></a>(define&nbsp;(mul-poly&nbsp;p1&nbsp;p2)<br />
  &nbsp;&nbsp;(if&nbsp;(same-variable?&nbsp;(variable&nbsp;p1)&nbsp;(variable&nbsp;p2))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(make-poly&nbsp;(variable&nbsp;p1)<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(mul-terms&nbsp;(term-list&nbsp;p1)<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(term-list&nbsp;p2)))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(error&nbsp;"Polys&nbsp;not&nbsp;in&nbsp;same&nbsp;var&nbsp;--&nbsp;MUL-POLY"<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(list&nbsp;p1&nbsp;p2))))<br />
  </tt></p>

  <p>To incorporate polynomials into our generic arithmetic system,
  we need to supply them with type tags. We'll use the tag
  <tt>polynomial</tt>, 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 section&nbsp;<a href="#%_sec_2.5.1">2.5.1</a>:
  <a name="%_idx_2678"></a><a name="%_idx_2680"></a><a name="%_idx_2682"></a></p>

  <p><tt><a name="%_idx_2684"></a><a name="%_idx_2686"></a><a name="%_idx_2688"></a><a name="%_idx_2690"></a>(define&nbsp;(install-polynomial-package)<br />
  &nbsp;&nbsp;<em>;;&nbsp;internal&nbsp;procedures</em><br />
  &nbsp;&nbsp;<em>;;&nbsp;representation&nbsp;of&nbsp;poly</em><br />
  &nbsp;&nbsp;(define&nbsp;(make-poly&nbsp;variable&nbsp;term-list)<br />

  &nbsp;&nbsp;&nbsp;&nbsp;(cons&nbsp;variable&nbsp;term-list))<br />
  &nbsp;&nbsp;(define&nbsp;(variable&nbsp;p)&nbsp;(car&nbsp;p))<br />
  &nbsp;&nbsp;(define&nbsp;(term-list&nbsp;p)&nbsp;(cdr&nbsp;p))<br />

  &nbsp;&nbsp;&lt;<em>procedures&nbsp;<tt>same-variable?</tt>&nbsp;and&nbsp;<tt>variable?</tt>&nbsp;from&nbsp;section&nbsp;<a href="book-Z-H-16.html#%_sec_2.3.2">2.3.2</a></em>&gt;<br />

  &nbsp;&nbsp;<em>;;&nbsp;representation&nbsp;of&nbsp;terms&nbsp;and&nbsp;term&nbsp;lists</em><br />

  &nbsp;&nbsp;&lt;<em>procedures&nbsp;<tt>adjoin-term&nbsp;</tt>...</em><tt>coeff</tt></tt>&nbsp;from&nbsp;text&nbsp;below&gt;<br />

  <br />
  &nbsp;&nbsp;<em>;;&nbsp;continued&nbsp;on&nbsp;next&nbsp;page</em><br />

  <br />
  &nbsp;&nbsp;(define&nbsp;(add-poly&nbsp;p1&nbsp;p2)&nbsp;<tt>...</tt>)<br />

  &nbsp;&nbsp;&lt;<em>procedures&nbsp;used&nbsp;by&nbsp;<tt>add-poly</tt></em>&gt;<br />

  &nbsp;&nbsp;(define&nbsp;(mul-poly&nbsp;p1&nbsp;p2)&nbsp;<tt>...</tt>)<br />

  &nbsp;&nbsp;&lt;<em>procedures&nbsp;used&nbsp;by&nbsp;<tt>mul-poly</tt></em>&gt;<br />

  &nbsp;&nbsp;<em>;;&nbsp;interface&nbsp;to&nbsp;rest&nbsp;of&nbsp;the&nbsp;system</em><br />

  &nbsp;&nbsp;(define&nbsp;(tag&nbsp;p)&nbsp;(attach-tag&nbsp;'polynomial&nbsp;p))<br />

  &nbsp;&nbsp;(put&nbsp;'add&nbsp;'(polynomial&nbsp;polynomial)&nbsp;<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(lambda&nbsp;(p1&nbsp;p2)&nbsp;(tag&nbsp;(add-poly&nbsp;p1&nbsp;p2))))<br />

  &nbsp;&nbsp;(put&nbsp;'mul&nbsp;'(polynomial&nbsp;polynomial)&nbsp;<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(lambda&nbsp;(p1&nbsp;p2)&nbsp;(tag&nbsp;(mul-poly&nbsp;p1&nbsp;p2))))<br />

  &nbsp;&nbsp;(put&nbsp;'make&nbsp;'polynomial<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(lambda&nbsp;(var&nbsp;terms)&nbsp;(tag&nbsp;(make-poly&nbsp;var&nbsp;terms))))<br />

  &nbsp;&nbsp;'done)<br /></p>

  <p>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.</p>

  <p>In order to manipulate term lists, we will assume that we have
  a constructor <a name="%_idx_2692"></a><tt>the-empty-termlist</tt> that returns an
  empty term list and a constructor <a name="%_idx_2694"></a><tt>adjoin-term</tt> that adjoins a new term to
  a term list. We will also assume that we have a predicate
  <a name="%_idx_2696"></a><tt>empty-termlist?</tt> that tells if a
  given term list is empty, a selector <a name="%_idx_2698"></a><tt>first-term</tt> that extracts the
  highest-order term from a term list, and a selector <a name="%_idx_2700"></a><tt>rest-terms</tt> that returns all but the
  highest-order term. To manipulate terms, we will suppose that we
  have a constructor <a name="%_idx_2702"></a><tt>make-term</tt>
  that constructs a term with given order and coefficient, and
  selectors <a name="%_idx_2704"></a><tt>order</tt> and <a name="%_idx_2706"></a><tt>coeff</tt> 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.</p>

  <p>Here is the procedure that constructs the term list for the
  sum of two polynomials:<a href="#footnote_Temp_300" name="call_footnote_Temp_300" id="call_footnote_Temp_300"><sup><small>56</small></sup></a></p>

  <p><tt><a name="%_idx_2708"></a>(define&nbsp;(add-terms&nbsp;L1&nbsp;L2)<br />
  &nbsp;&nbsp;(cond&nbsp;((empty-termlist?&nbsp;L1)&nbsp;L2)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((empty-termlist?&nbsp;L2)&nbsp;L1)<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(let&nbsp;((t1&nbsp;(first-term&nbsp;L1))&nbsp;(t2&nbsp;(first-term&nbsp;L2)))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(cond&nbsp;((&gt;&nbsp;(order&nbsp;t1)&nbsp;(order&nbsp;t2))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(adjoin-term<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t1&nbsp;(add-terms&nbsp;(rest-terms&nbsp;L1)&nbsp;L2)))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((&lt;&nbsp;(order&nbsp;t1)&nbsp;(order&nbsp;t2))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(adjoin-term<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;t2&nbsp;(add-terms&nbsp;L1&nbsp;(rest-terms&nbsp;L2))))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(adjoin-term<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(make-term&nbsp;(order&nbsp;t1)<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(add&nbsp;(coeff&nbsp;t1)&nbsp;(coeff&nbsp;t2)))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(add-terms&nbsp;(rest-terms&nbsp;L1)<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(rest-terms&nbsp;L2)))))))))<br />
  </tt></p>

  <p>The most important point to note here is that we used the
  generic addition procedure <a name="%_idx_2710"></a><tt>add</tt>
  to add together the coefficients of the terms being combined.
  This has powerful consequences, as we will see below.</p>

  <p>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 <tt>mul-term-by-all-terms</tt>, 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:</p>

  <p><tt><a name="%_idx_2712"></a>(define&nbsp;(mul-terms&nbsp;L1&nbsp;L2)<br />
  &nbsp;&nbsp;(if&nbsp;(empty-termlist?&nbsp;L1)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(the-empty-termlist)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(add-terms&nbsp;(mul-term-by-all-terms&nbsp;(first-term&nbsp;L1)&nbsp;L2)<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(mul-terms&nbsp;(rest-terms&nbsp;L1)&nbsp;L2))))<br />

  (define&nbsp;(mul-term-by-all-terms&nbsp;t1&nbsp;L)<br />
  &nbsp;&nbsp;(if&nbsp;(empty-termlist?&nbsp;L)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(the-empty-termlist)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(let&nbsp;((t2&nbsp;(first-term&nbsp;L)))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(adjoin-term<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(make-term&nbsp;(+&nbsp;(order&nbsp;t1)&nbsp;(order&nbsp;t2))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(mul&nbsp;(coeff&nbsp;t1)&nbsp;(coeff&nbsp;t2)))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(mul-term-by-all-terms&nbsp;t1&nbsp;(rest-terms&nbsp;L))))))<br />
  </tt></p>

  <p>This is really all there is to polynomial addition and
  multiplication. <a name="%_idx_2714"></a><a name="%_idx_2716"></a>Notice that, since we operate on terms using the
  generic procedures <tt>add</tt> and <tt>mul</tt>, 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 <a name="%_idx_2718"></a>coercion mechanism such as one
  of those discussed in section&nbsp;<a href="#%_sec_2.5.2">2.5.2</a>, then we also are automatically able to
  handle operations on polynomials of different coefficient types,
  such as</p>

  <div align="left"><img src="ch2-Z-G-71.gif" border="0" /></div>

  <p>Because we installed the polynomial addition and
  multiplication procedures <tt>add-poly</tt> and <tt>mul-poly</tt>
  in the generic arithmetic system as the <tt>add</tt> and
  <tt>mul</tt> operations for type <tt>polynomial</tt>, our system
  is also automatically able to handle polynomial operations such
  as</p>

  <div align="left"><img src="ch2-Z-G-72.gif" border="0" /></div>

  <p>The reason is that when the system tries to combine
  coefficients, it will dispatch through <tt>add</tt> and
  <tt>mul</tt>. Since the coefficients are themselves polynomials
  (in <em>y</em>), these will be combined using <tt>add-poly</tt>
  and <tt>mul-poly</tt>. The result is a kind of <a name="%_idx_2720"></a><a name="%_idx_2722"></a>``data-directed
  recursion'' in which, for example, a call to <tt>mul-poly</tt>
  will result in recursive calls to <tt>mul-poly</tt> 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.<a href="#footnote_Temp_301" name="call_footnote_Temp_301" id="call_footnote_Temp_301"><sup><small>57</small></sup></a>
  <a name="%_sec_Temp_302"></a></p>

  <h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_302">Representing
  term lists</a></h4>

  <p><a name="%_idx_2724"></a> 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 section&nbsp;<a href="book-Z-H-16.html#%_sec_2.3.3">2.3.3</a>, can be applied to this
  task. On the other hand, our procedures <tt>add-terms</tt> and
  <tt>mul-terms</tt> always access term lists sequentially from
  highest to lowest order. Thus, we will use some kind of ordered
  list representation.</p>

  <p>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 <a name="%_idx_2726"></a><a name="%_idx_2728"></a><em>dense</em> if it
  has nonzero coefficients in terms of most orders. If it has many
  zero terms it is said to be <a name="%_idx_2730"></a><a name="%_idx_2732"></a><em>sparse</em>. For example,</p>

  <div align="left"><img src="ch2-Z-G-74.gif" border="0" /></div>

  <p>is a dense polynomial, whereas</p>

  <div align="left"><img src="ch2-Z-G-75.gif" border="0" /></div>

  <p>is sparse.</p>

  <p>The term lists of dense polynomials are most efficiently
  represented as lists of the coefficients. For example, <em>A</em>
  above would be nicely represented as <tt>(1 2 0 3 -2 -5)</tt>.
  The order of a term in this representation is the length of the
  sublist beginning with that term's coefficient, decremented by
  1.<a href="#footnote_Temp_303" name="call_footnote_Temp_303" id="call_footnote_Temp_303"><sup><small>58</small></sup></a> This
  would be a terrible representation for a sparse polynomial such
  as <em>B</em>: 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
  <em>B</em> is efficiently represented as <tt>((100 1) (2 2) (0
  1))</tt>. 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 href="#footnote_Temp_304" name="call_footnote_Temp_304" id="call_footnote_Temp_304"><sup><small>59</small></sup></a></p>

  <p><tt><a name="%_idx_2734"></a>(define&nbsp;(adjoin-term&nbsp;term&nbsp;term-list)<br />

  &nbsp;&nbsp;(if&nbsp;(=zero?&nbsp;(coeff&nbsp;term))<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;term-list<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(cons&nbsp;term&nbsp;term-list)))<br />

  <a name="%_idx_2736"></a>(define&nbsp;(the-empty-termlist)&nbsp;'())<br />
  <a name="%_idx_2738"></a>(define&nbsp;(first-term&nbsp;term-list)&nbsp;(car&nbsp;term-list))<br />

  <a name="%_idx_2740"></a>(define&nbsp;(rest-terms&nbsp;term-list)&nbsp;(cdr&nbsp;term-list))<br />

  <a name="%_idx_2742"></a>(define&nbsp;(empty-termlist?&nbsp;term-list)&nbsp;(null?&nbsp;term-list))<br />

  <a name="%_idx_2744"></a>(define&nbsp;(make-term&nbsp;order&nbsp;coeff)&nbsp;(list&nbsp;order&nbsp;coeff))<br />

  <a name="%_idx_2746"></a>(define&nbsp;(order&nbsp;term)&nbsp;(car&nbsp;term))<br />

  <a name="%_idx_2748"></a>(define&nbsp;(coeff&nbsp;term)&nbsp;(cadr&nbsp;term))<br />
  </tt></p>

  <p>where <tt>=zero?</tt> is as defined in exercise&nbsp;<a href="#%_thm_2.80">2.80</a>. (See also exercise&nbsp;<a href="#%_thm_2.87">2.87</a> below.)</p>

  <p>Users of the polynomial package will create (tagged)
  polynomials by means of the procedure:</p>

  <p><tt><a name="%_idx_2750"></a>(define&nbsp;(make-polynomial&nbsp;var&nbsp;terms)<br />

  &nbsp;&nbsp;((get&nbsp;'make&nbsp;'polynomial)&nbsp;var&nbsp;terms))<br />
  </tt></p>

  <p><a name="%_thm_2.87"></a> <b>Exercise
  2.87.</b>&nbsp;&nbsp;<a name="%_idx_2752"></a><a name="%_idx_2754"></a>Install <tt>=zero?</tt> for polynomials in the
  generic arithmetic package. This will allow <tt>adjoin-term</tt>
  to work for polynomials with coefficients that are themselves
  polynomials.</p>

  <p><a name="%_thm_2.88"></a> <b>Exercise
  2.88.</b>&nbsp;&nbsp;<a name="%_idx_2756"></a>Extend the
  polynomial system to include subtraction of polynomials. (Hint:
  You may find it helpful to define a generic negation
  operation.)</p>

  <p><a name="%_thm_2.89"></a> <b>Exercise
  2.89.</b>&nbsp;&nbsp;Define procedures that implement the
  term-list representation described above as appropriate for dense
  polynomials.</p>

  <p><a name="%_thm_2.90"></a> <b>Exercise
  2.90.</b>&nbsp;&nbsp;Suppose we want to have a polynomial system
  that is efficient for both sparse and dense polynomials. One way
  to do this is to allow both kinds of term-list representations in
  our system. The situation is analogous to the complex-number
  example of section&nbsp;<a href="book-Z-H-17.html#%_sec_2.4">2.4</a>, where we allowed both
  rectangular and polar representations. To do this we must
  distinguish different types of term lists and make the operations
  on term lists generic. Redesign the polynomial system to
  implement this generalization. This is a major effort, not a
  local change.</p>

  <p><a name="%_thm_2.91"></a> <b>Exercise
  2.91.</b>&nbsp;&nbsp;<a name="%_idx_2758"></a>A univariate
  polynomial can be divided by another one to produce a polynomial
  quotient and a polynomial remainder. For example,</p>

  <div align="left"><img src="ch2-Z-G-76.gif" border="0" /></div>

  <p>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.</p>

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

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

  <p><tt><a name="%_idx_2762"></a>(define&nbsp;(div-terms&nbsp;L1&nbsp;L2)<br />
  &nbsp;&nbsp;(if&nbsp;(empty-termlist?&nbsp;L1)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(list&nbsp;(the-empty-termlist)&nbsp;(the-empty-termlist))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(let&nbsp;((t1&nbsp;(first-term&nbsp;L1))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(t2&nbsp;(first-term&nbsp;L2)))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(if&nbsp;(&gt;&nbsp;(order&nbsp;t2)&nbsp;(order&nbsp;t1))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(list&nbsp;(the-empty-termlist)&nbsp;L1)<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(let&nbsp;((new-c&nbsp;(div&nbsp;(coeff&nbsp;t1)&nbsp;(coeff&nbsp;t2)))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(new-o&nbsp;(-&nbsp;(order&nbsp;t1)&nbsp;(order&nbsp;t2))))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(let&nbsp;((rest-of-result<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&lt;<em>compute&nbsp;rest&nbsp;of&nbsp;result&nbsp;recursively</em>&gt;<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;))<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&lt;<em>form&nbsp;complete&nbsp;result</em>&gt;<br />

  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;))))))<br />
  </tt></p>

  <p><a name="%_sec_Temp_310"></a></p>

  <h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_310">Hierarchies of
  types in symbolic algebra</a></h4>

  <p><a name="%_idx_2764"></a><a name="%_idx_2766"></a><a name="%_idx_2768"></a> 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.</p>

  <p>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 <em>x</em> whose
  coefficients are polynomials in <em>y</em>. It is also possible
  to have polynomials in <em>y</em> whose coefficients are
  polynomials in <em>x</em>. 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 <a name="%_idx_2770"></a><a name="%_idx_2772"></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.</p>

  <p>It should not be surprising that controlling <a name="%_idx_2774"></a>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.</p>

  <p><a name="%_thm_2.92"></a> <b>Exercise 2.92.</b>&nbsp;&nbsp;By
  imposing an ordering on variables, extend the polynomial package
  so that addition and multiplication of polynomials works for
  polynomials in different variables. (This is not easy!)</p>

  <p><a name="%_sec_Temp_312"></a></p>

  <h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_312">Extended
  exercise: Rational functions</a></h4>

  <p><a name="%_idx_2776"></a><a name="%_idx_2778"></a><a name="%_idx_2780"></a>We can extend our generic arithmetic system to
  include <em>rational functions</em>. These are ``fractions''
  whose numerator and denominator are polynomials, such as</p>

  <div align="left"><img src="ch2-Z-G-77.gif" border="0" /></div>

  <p>The system should be able to add, subtract, multiply, and
  divide rational functions, and to perform such computations
  as</p>

  <div align="left"><img src="ch2-Z-G-78.gif" border="0" /></div>

  <p>(Here the sum has been simplified by removing common factors.
  Ordinary ``cross multiplication'' would have produced a
  fourth-degree polynomial over a fifth-degree polynomial.)</p>

  <p>If we modify our rational-arithmetic package so that it uses
  generic operations, then it will do what we want, except for the
  problem of reducing fractions to lowest terms.</p>

  <p><a name="%_thm_2.93"></a> <b>Exercise
  2.93.</b>&nbsp;&nbsp;Modify the rational-arithmetic package to
  use generic operations, but change <tt>make-rat</tt> so that it
  does not attempt to reduce fractions to lowest terms. Test your
  system by calling <tt>make-rational</tt> on two polynomials to
  produce a rational function</p>

  <p>
  <tt>(define&nbsp;p1&nbsp;(make-polynomial&nbsp;'x&nbsp;'((2&nbsp;1)(0&nbsp;1))))<br />

  (define&nbsp;p2&nbsp;(make-polynomial&nbsp;'x&nbsp;'((3&nbsp;1)(0&nbsp;1))))<br />

  (define&nbsp;rf&nbsp;(make-rational&nbsp;p2&nbsp;p1))<br /></tt></p>

  <p>Now add <tt>rf</tt> to itself, using <tt>add</tt>. You will
  observe that this addition procedure does not reduce fractions to
  lowest terms.</p>

  <p>We can reduce polynomial fractions to lowest terms using the
  same idea we used with integers: modifying <tt>make-rat</tt> to
  divide both the numerator and the denominator by their greatest
  common divisor. The notion of <a name="%_idx_2782"></a><a name="%_idx_2784"></a>``greatest common divisor'' makes sense for
  polynomials. In fact, we can compute the GCD of two polynomials
  using essentially the same Euclid's Algorithm that works for
  integers.<a href="#footnote_Temp_314" name="call_footnote_Temp_314" id="call_footnote_Temp_314"><sup><small>60</small></sup></a> The
  integer version is</p>

  <p><tt>(define&nbsp;(gcd&nbsp;a&nbsp;b)<br />
  &nbsp;&nbsp;(if&nbsp;(=&nbsp;b&nbsp;0)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(gcd&nbsp;b&nbsp;(remainder&nbsp;a&nbsp;b))))<br />
  </tt></p>

  <p>Using this, we could make the obvious modification to define a
  GCD operation that works on term lists:</p>

  <p><tt><a name="%_idx_2794"></a>(define&nbsp;(gcd-terms&nbsp;a&nbsp;b)<br />
  &nbsp;&nbsp;(if&nbsp;(empty-termlist?&nbsp;b)<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a<br />
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(gcd-terms&nbsp;b&nbsp;(remainder-terms&nbsp;a&nbsp;b))))<br />
  </tt></p>

  <p>where <tt>remainder-terms</tt> picks out the remainder
  component of the list returned by the term-list division
  operation <tt>div-terms</tt> that was implemented in
  exercise&nbsp;<a href="#%_thm_2.91">2.91</a>.</p>

  <p><a name="%_thm_2.94"></a> <b>Exercise
  2.94.</b>&nbsp;&nbsp;<a name="%_idx_2796"></a><a name="%_idx_2798"></a>Using <tt>div-terms</tt>, implement the
  procedure <tt>remainder-terms</tt> and use this to define
  <tt>gcd-terms</tt> as above. Now write a procedure
  <tt>gcd-poly</tt> that computes the polynomial GCD of two polys.
  (The procedure should signal an error if the two polys are not in
  the same variable.) Install in the system a generic operation
  <tt>greatest-common-divisor</tt> that reduces to
  <tt>gcd-poly</tt> for polynomials and to ordinary <tt>gcd</tt>
  for ordinary numbers. As a test, try</p>

  <p>
  <tt>(define&nbsp;p1&nbsp;(make-polynomial&nbsp;'x&nbsp;'((4&nbsp;1)&nbsp;(3&nbsp;-1)&nbsp;(2&nbsp;-2)&nbsp;(1&nbsp;2))))<br />

  (define&nbsp;p2&nbsp;(make-polynomial&nbsp;'x&nbsp;'((3&nbsp;1)&nbsp;(1&nbsp;-1))))<br />

  (greatest-common-divisor&nbsp;p1&nbsp;p2)<br /></tt></p>

  <p>and check your result by hand.</p>

  <p><a name="%_thm_2.95"></a> <b>Exercise
  2.95.</b>&nbsp;&nbsp;Define <em>P</em><sub>1</sub>,
  <em>P</em><sub>2</sub>, and <em>P</em><sub>3</sub> to be the
  polynomials</p>

  <div align="left"><img src="ch2-Z-G-79.gif" border="0" /></div>

  <div align="left"><img src="ch2-Z-G-80.gif" border="0" /></div>

  <div align="left"><img src="ch2-Z-G-81.gif" border="0" /></div>

  <p>Now define <em>Q</em><sub>1</sub> to be the product of
  <em>P</em><sub>1</sub> and <em>P</em><sub>2</sub> and
  <em>Q</em><sub>2</sub> to be the product of
  <em>P</em><sub>1</sub> and <em>P</em><sub>3</sub>, and use
  <tt>greatest-common-divisor</tt> (exercise&nbsp;<a href="#%_thm_2.94">2.94</a>) to compute the GCD of
  <em>Q</em><sub>1</sub> and <em>Q</em><sub>2</sub>. Note that the
  answer is not the same as <em>P</em><sub>1</sub>. This example
  introduces noninteger operations into the computation, causing
  difficulties with the GCD algorithm.<a href="#footnote_Temp_317" name="call_footnote_Temp_317" id="call_footnote_Temp_317"><sup><small>61</small></sup></a> To
  understand what is happening, try tracing <tt>gcd-terms</tt>
  while computing the GCD or try performing the division by
  hand.</p>

  <p>We can solve the problem exhibited in exercise&nbsp;<a href="#%_thm_2.95">2.95</a> if we use the following modification of
  the GCD algorithm (which really works only in the case of
  polynomials with integer coefficients). Before performing any
  polynomial division in the GCD computation, we multiply the
  dividend by an integer constant factor, chosen to guarantee that
  no fractions will arise during the division process. Our answer
  will thus differ from the actual GCD by an integer constant
  factor, but this does not matter in the case of reducing rational
  functions to lowest terms; the GCD will be used to divide both
  the numerator and denominator, so the integer constant factor
  will cancel out.</p>

  <p>More precisely, if <em>P</em> and <em>Q</em> are polynomials,
  let <em>O</em><sub>1</sub> be the order of <em>P</em> (i.e., the
  order of the largest term of <em>P</em>) and let
  <em>O</em><sub>2</sub> be the order of <em>Q</em>. Let <em>c</em>
  be the leading coefficient of <em>Q</em>. Then it can be shown
  that, if we multiply <em>P</em> by the <a name="%_idx_2800"></a><em>integerizing factor</em>
  <em>c</em><sup>1+<em>O</em><sub>1</sub>
  -<em>O</em><sub>2</sub></sup>, the resulting polynomial can be
  divided by <em>Q</em> by using the <tt>div-terms</tt> algorithm
  without introducing any fractions. The operation of multiplying
  the dividend by this constant and then dividing is sometimes
  called the <a name="%_idx_2802"></a><a name="%_idx_2804"></a><em>pseudodivision</em> of <em>P</em> by
  <em>Q</em>. The remainder of the division is called the
  <em>pseudoremainder</em>.</p>

  <p><a name="%_thm_2.96"></a> <b>Exercise
  2.96.</b>&nbsp;&nbsp;a.&nbsp;&nbsp;&nbsp;&nbsp;Implement the
  procedure <tt>pseudoremainder-terms</tt>, which is just like
  <tt>remainder-terms</tt> except that it multiplies the dividend
  by the integerizing factor described above before calling
  <tt>div-terms</tt>. Modify <tt>gcd-terms</tt> to use
  <tt>pseudoremainder-terms</tt>, and verify that
  <tt>greatest-common-divisor</tt> now produces an answer with
  integer coefficients on the example in exercise&nbsp;<a href="#%_thm_2.95">2.95</a>.</p>

  <p>b.&nbsp;&nbsp;&nbsp;&nbsp;The GCD now has integer
  coefficients, but they are larger than those of
  <em>P</em><sub>1</sub>. Modify <tt>gcd-terms</tt> so that it
  removes common factors from the coefficients of the answer by
  dividing all the coefficients by their (integer) greatest common
  divisor.</p>

  <p><a name="%_idx_2806"></a><a name="%_idx_2808"></a>Thus, here
  is how to reduce a rational function to lowest terms:</p>

  <ul>
    <li>Compute the GCD of the numerator and denominator, using the
    version of <tt>gcd-terms</tt> from exercise&nbsp;<a href="#%_thm_2.96">2.96</a>.</li>

    <li>When you obtain the GCD, multiply both numerator and
    denominator by the same integerizing factor before dividing
    through by the GCD, so that division by the GCD will not
    introduce any noninteger coefficients. As the factor you can
    use the leading coefficient of the GCD raised to the power 1 +
    <em>O</em><sub>1</sub> - <em>O</em><sub>2</sub>, where
    <em>O</em><sub>2</sub> is the order of the GCD and
    <em>O</em><sub>1</sub> is the maximum of the orders of the
    numerator and denominator. This will ensure that dividing the
    numerator and denominator by the GCD will not introduce any
    fractions.</li>

    <li>The result of this operation will be a numerator and
    denominator with integer coefficients. The coefficients will
    normally be very large because of all of the integerizing
    factors, so the last step is to remove the redundant factors by
    computing the (integer) greatest common divisor of all the
    coefficients of the numerator and the denominator and dividing
    through by this factor.</li>
  </ul>

  <p><a name="%_thm_2.97"></a> <b>Exercise 2.97.</b>&nbsp;&nbsp;a.
  Implement this algorithm as a procedure <tt>reduce-terms</tt>
  that takes two term lists <tt>n</tt> and <tt>d</tt> as arguments
  and returns a list <tt>nn</tt>, <tt>dd</tt>, which are <tt>n</tt>
  and <tt>d</tt> reduced to lowest terms via the algorithm given
  above. Also write a procedure <tt>reduce-poly</tt>, analogous to
  <tt>add-poly</tt>, that checks to see if the two polys have the
  same variable. If so, <tt>reduce-poly</tt> strips off the
  variable and passes the problem to <tt>reduce-terms</tt>, then
  reattaches the variable to the two term lists supplied by
  <tt>reduce-terms</tt>.</p>

  <p>b. Define a procedure analogous to <tt>reduce-terms</tt> that
  does what the original <tt>make-rat</tt> did for integers:</p>

  <p><tt>(define&nbsp;(reduce-integers&nbsp;n&nbsp;d)<br />
  &nbsp;&nbsp;(let&nbsp;((g&nbsp;(gcd&nbsp;n&nbsp;d)))<br />
  &nbsp;&nbsp;&nbsp;&nbsp;(list&nbsp;(/&nbsp;n&nbsp;g)&nbsp;(/&nbsp;d&nbsp;g))))<br />
  </tt></p>

  <p>and define <tt>reduce</tt> as a generic operation that calls
  <tt>apply-generic</tt> to dispatch to either <tt>reduce-poly</tt>
  (for <tt>polynomial</tt> arguments) or <tt>reduce-integers</tt>
  (for <tt>scheme-number</tt> arguments). You can now easily make
  the rational-arithmetic package reduce fractions to lowest terms
  by having <tt>make-rat</tt> call <tt>reduce</tt> before combining
  the given numerator and denominator to form a rational number.
  The system now handles rational expressions in either integers or
  polynomials. To test your program, try the example at the
  beginning of this extended exercise:</p>

  <p>
  <tt>(define&nbsp;p1&nbsp;(make-polynomial&nbsp;'x&nbsp;'((1&nbsp;1)(0&nbsp;1))))<br />

  (define&nbsp;p2&nbsp;(make-polynomial&nbsp;'x&nbsp;'((3&nbsp;1)(0&nbsp;-1))))<br />

  (define&nbsp;p3&nbsp;(make-polynomial&nbsp;'x&nbsp;'((1&nbsp;1))))<br />

  (define&nbsp;p4&nbsp;(make-polynomial&nbsp;'x&nbsp;'((2&nbsp;1)(0&nbsp;-1))))<br />

  <br />
  (define&nbsp;rf1&nbsp;(make-rational&nbsp;p1&nbsp;p2))<br />
  (define&nbsp;rf2&nbsp;(make-rational&nbsp;p3&nbsp;p4))<br />
  <br />
  (add&nbsp;rf1&nbsp;rf2)<br /></tt></p>

  <p>See if you get the correct answer, correctly reduced to lowest
  terms.</p>

  <p>The GCD computation is at the heart of any system that does
  operations on rational functions. The algorithm used above,
  although mathematically straightforward, is extremely slow. The
  slowness is due partly to the large number of division operations
  and partly to the enormous size of the intermediate coefficients
  generated by the pseudodivisions. One of the active areas in the
  development of algebraic-manipulation systems is the design of
  better algorithms for computing polynomial GCDs.<a href="#footnote_Temp_320" name="call_footnote_Temp_320" id="call_footnote_Temp_320"><sup><small>62</small></sup></a></p>

  <div class="smallprint">
    <hr />
  </div>

  <div class="footnote">
    <p><a href="#call_footnote_Temp_283" name="footnote_Temp_283" id="footnote_Temp_283"><sup><small>49</small></sup></a> We also
    have to supply an almost identical procedure to handle the
    types <tt>(scheme-number complex)</tt>.</p>

    <p><a href="#call_footnote_Temp_285" name="footnote_Temp_285" id="footnote_Temp_285"><sup><small>50</small></sup></a> See
    exercise&nbsp;<a href="#%_thm_2.82">2.82</a> for
    generalizations.</p>

    <p><a href="#call_footnote_Temp_286" name="footnote_Temp_286" id="footnote_Temp_286"><sup><small>51</small></sup></a> If we
    are clever, we can usually get by with fewer than
    <em>n</em><sup>2</sup> coercion procedures. For instance, if we
    know how to convert from type 1 to type 2 and from type 2 to
    type 3, then we can use this knowledge to convert from type 1
    to type 3. This can greatly decrease the number of coercion
    procedures we need to supply explicitly when we add a new type
    to the system. If we are willing to build the required amount
    of sophistication into our system, we can have it search the
    ``graph'' of relations among types and automatically generate
    those coercion procedures that can be inferred from the ones
    that are supplied explicitly.</p>

    <p><a href="#call_footnote_Temp_289" name="footnote_Temp_289" id="footnote_Temp_289"><sup><small>52</small></sup></a> This
    statement, which also appears in the first edition of this
    book, is just as true now as it was when we wrote it twelve
    years ago. Developing a useful, general framework for
    expressing the relations among different types of entities
    (what philosophers call ``ontology'') seems intractably
    difficult. The main difference between the confusion that
    existed ten years ago and the confusion that exists now is that
    now a variety of inadequate ontological theories have been
    embodied in a plethora of correspondingly inadequate
    programming languages. For example, much of the complexity of
    <a name="%_idx_2622"></a><a name="%_idx_2624"></a>object-oriented programming languages -- and
    the subtle and confusing differences among contemporary
    object-oriented languages -- centers on the treatment of
    generic operations on interrelated types. Our own discussion of
    computational objects in chapter&nbsp;3 avoids these issues
    entirely. Readers familiar with object-oriented programming
    will notice that we have much to say in chapter&nbsp;3 about
    local state, but we do not even mention ``classes'' or
    ``inheritance.'' In fact, we suspect that these problems cannot
    be adequately addressed in terms of computer-language design
    alone, without also drawing on work in knowledge representation
    and automated reasoning.</p>

    <p><a href="#call_footnote_Temp_295" name="footnote_Temp_295" id="footnote_Temp_295"><sup><small>53</small></sup></a> A real
    number can be projected to an integer using the <a name="%_idx_2642"></a><a name="%_idx_2644"></a><tt>round</tt>
    primitive, which returns the closest integer to its
    argument.</p>

    <p><a href="#call_footnote_Temp_298" name="footnote_Temp_298" id="footnote_Temp_298"><sup><small>54</small></sup></a> On the
    other hand, we will allow polynomials whose coefficients are
    themselves polynomials in other variables. This will give us
    essentially the same representational power as a full
    multivariate system, although it does lead to coercion
    problems, as discussed below.</p>

    <p><a href="#call_footnote_Temp_299" name="footnote_Temp_299" id="footnote_Temp_299"><sup><small>55</small></sup></a> For
    univariate polynomials, giving the value of a polynomial at a
    given set of points can be a particularly good representation.
    This makes polynomial arithmetic extremely simple. To obtain,
    for example, the sum of two polynomials represented in this
    way, we need only add the values of the polynomials at
    corresponding points. To transform back to a more familiar
    representation, we can use the <a name="%_idx_2662"></a>Lagrange interpolation formula, which shows
    how to recover the coefficients of a polynomial of degree
    <em>n</em> given the values of the polynomial at <em>n</em> + 1
    points.</p>

    <p><a href="#call_footnote_Temp_300" name="footnote_Temp_300" id="footnote_Temp_300"><sup><small>56</small></sup></a> This
    operation is very much like the ordered <tt>union-set</tt>
    operation we developed in exercise &nbsp;<a href="book-Z-H-16.html#%_thm_2.62">2.62</a>. In fact, if we think of
    the terms of the polynomial as a set ordered according to the
    power of the indeterminate, then the program that produces the
    term list for a sum is almost identical to
    <tt>union-set</tt>.</p>

    <p><a href="#call_footnote_Temp_301" name="footnote_Temp_301" id="footnote_Temp_301"><sup><small>57</small></sup></a> To make
    this work completely smoothly, we should also add to our
    generic arithmetic system the ability to coerce a ``number'' to
    a polynomial by regarding it as a polynomial of degree zero
    whose coefficient is the number. This is necessary if we are
    going to perform operations such as</p>

    <div align="left"><img src="ch2-Z-G-73.gif" border="0" /></div>

    <p>which requires adding the coefficient <em>y</em> + 1 to the
    coefficient 2.</p>

    <p><a href="#call_footnote_Temp_303" name="footnote_Temp_303" id="footnote_Temp_303"><sup><small>58</small></sup></a> In
    these polynomial examples, we assume that we have implemented
    the generic arithmetic system using the type mechanism
    suggested in exercise&nbsp;<a href="#%_thm_2.78">2.78</a>.
    Thus, coefficients that are ordinary numbers will be
    represented as the numbers themselves rather than as pairs
    whose <tt>car</tt> is the symbol <tt>scheme-number</tt>.</p>

    <p><a href="#call_footnote_Temp_304" name="footnote_Temp_304" id="footnote_Temp_304"><sup><small>59</small></sup></a>
    Although we are assuming that term lists are ordered, we have
    implemented <tt>adjoin-term</tt> to simply <tt>cons</tt> the
    new term onto the existing term list. We can get away with this
    so long as we guarantee that the procedures (such as
    <tt>add-terms</tt>) that use <tt>adjoin-term</tt> always call
    it with a higher-order term than appears in the list. If we did
    not want to make such a guarantee, we could have implemented
    <tt>adjoin-term</tt> to be similar to the <tt>adjoin-set</tt>
    constructor for the ordered-list representation of sets
    (exercise&nbsp;<a href="book-Z-H-16.html#%_thm_2.61">2.61</a>).</p>

    <p><a href="#call_footnote_Temp_314" name="footnote_Temp_314" id="footnote_Temp_314"><sup><small>60</small></sup></a> The
    fact that <a name="%_idx_2786"></a><a name="%_idx_2788"></a>Euclid's Algorithm works for polynomials is
    formalized in algebra by saying that polynomials form a kind of
    algebraic domain called a <a name="%_idx_2790"></a><a name="%_idx_2792"></a><em>Euclidean ring</em>. A Euclidean ring is a
    domain that admits addition, subtraction, and commutative
    multiplication, together with a way of assigning to each
    element <em>x</em> of the ring a positive integer ``measure''
    <em>m</em>(<em>x</em>) with the properties that
    <em>m</em>(<em>x</em><em>y</em>)<u>&gt;</u>
    <em>m</em>(<em>x</em>) for any nonzero <em>x</em> and
    <em>y</em> and that, given any <em>x</em> and <em>y</em>, there
    exists a <em>q</em> such that <em>y</em> = <em>q</em><em>x</em>
    + <em>r</em> and either <em>r</em> = 0 or
    <em>m</em>(<em>r</em>)&lt; <em>m</em>(<em>x</em>). From an
    abstract point of view, this is what is needed to prove that
    Euclid's Algorithm works. For the domain of integers, the
    measure <em>m</em> of an integer is the absolute value of the
    integer itself. For the domain of polynomials, the measure of a
    polynomial is its degree.</p>

    <p><a href="#call_footnote_Temp_317" name="footnote_Temp_317" id="footnote_Temp_317"><sup><small>61</small></sup></a> In an
    implementation like MIT Scheme, this produces a polynomial that
    is indeed a divisor of <em>Q</em><sub>1</sub> and
    <em>Q</em><sub>2</sub>, but with rational coefficients. In many
    other Scheme systems, in which division of integers can produce
    limited-precision decimal numbers, we may fail to get a valid
    divisor.</p>

    <p><a href="#call_footnote_Temp_320" name="footnote_Temp_320" id="footnote_Temp_320"><sup><small>62</small></sup></a> One
    extremely efficient and elegant method for computing <a name="%_idx_2810"></a><a name="%_idx_2812"></a><a name="%_idx_2814"></a><a name="%_idx_2816"></a>polynomial GCDs was
    discovered by <a name="%_idx_2818"></a>Richard Zippel (1979).
    The method is a probabilistic algorithm, as is the fast test
    for primality that we discussed in chapter&nbsp;1. Zippel's
    book (1993) describes this method, together with other ways to
    compute polynomial GCDs.</p>
  </div>

  
</body>
</html>