Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
tree: abd4721059
Fetching contributors…

Cannot retrieve contributors at this time

1141 lines (880 sloc) 58.127 kb
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN" "http://www.w3.org/TR/REC-html40/loose.dtd">
<html>
<!-- Generated from TeX source by tex2page, v 4o,
(c) Dorai Sitaram, http://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.4"></a></p>
<h2><a href="book-Z-H-4.html#%_toc_%_sec_2.4">2.4&nbsp;&nbsp;Multiple
Representations for Abstract Data</a></h2>
<p><a name="%_idx_2286"></a><a name="%_idx_2288"></a> We have
introduced data abstraction, a methodology for structuring
systems in such a way that much of a program can be specified
independent of the choices involved in implementing the data
objects that the program manipulates. For example, we saw in
section&nbsp;<a href="book-Z-H-14.html#%_sec_2.1.1">2.1.1</a> how
to separate the task of designing a program that uses rational
numbers from the task of implementing rational numbers in terms
of the computer language's primitive mechanisms for constructing
compound data. The key idea was to erect an abstraction barrier
-- in this case, the selectors and constructors for rational
numbers (<tt>make-rat</tt>, <tt>numer</tt>, <tt>denom</tt>) --
that isolates the way rational numbers are used from their
underlying representation in terms of list structure. A similar
abstraction barrier isolates the details of the procedures that
perform rational arithmetic (<tt>add-rat</tt>, <tt>sub-rat</tt>,
<tt>mul-rat</tt>, and <tt>div-rat</tt>) from the ``higher-level''
procedures that use rational numbers. The resulting program has
the structure shown in figure&nbsp;<a href="book-Z-H-14.html#%_fig_2.1">2.1</a>.</p>
<p>These data-abstraction barriers are powerful tools for
controlling complexity. By isolating the underlying
representations of data objects, we can divide the task of
designing a large program into smaller tasks that can be
performed separately. But this kind of data abstraction is not
yet powerful enough, because it may not always make sense to
speak of ``the underlying representation'' for a data object.</p>
<p>For one thing, there might be more than one useful
representation for a data object, and we might like to design
systems that can deal with multiple representations. To take a
simple example, complex numbers may be represented in two almost
equivalent ways: in rectangular form (real and imaginary parts)
and in polar form (magnitude and angle). Sometimes rectangular
form is more appropriate and sometimes polar form is more
appropriate. Indeed, it is perfectly plausible to imagine a
system in which complex numbers are represented in both ways, and
in which the procedures for manipulating complex numbers work
with either representation.</p>
<p>More importantly, programming systems are often designed by
many people working over extended periods of time, subject to
requirements that change over time. In such an environment, it is
simply not possible for everyone to agree in advance on choices
of data representation. So in addition to the data-abstraction
barriers that isolate representation from use, we need
abstraction barriers that isolate different design choices from
each other and permit different choices to coexist in a single
program. Furthermore, since large programs are often created by
combining pre-existing modules that were designed in isolation,
we need conventions that permit programmers to incorporate
modules into larger systems <a name="%_idx_2290"></a><em>additively</em>, that is, without having to
redesign or reimplement these modules.</p>
<p>In this section, we will learn how to cope with data that may
be represented in different ways by different parts of a program.
This requires constructing <a name="%_idx_2292"></a><a name="%_idx_2294"></a><em>generic procedures</em> -- procedures that
can operate on data that may be represented in more than one way.
Our main technique for building generic procedures will be to
work in terms of data objects that have <a name="%_idx_2296"></a><em>type tags</em>, that is, data objects that
include explicit information about how they are to be processed.
We will also discuss <a name="%_idx_2298"></a><em>data-directed</em> programming, a powerful
and convenient implementation strategy for additively assembling
systems with generic operations.</p>
<p>We begin with the simple complex-number example. We will see
how type tags and data-directed style enable us to design
separate rectangular and polar representations for complex
numbers while maintaining the notion of an abstract
``complex-number'' data object. <a name="%_idx_2300"></a><a name="%_idx_2302"></a>We will accomplish this by defining arithmetic
procedures for complex numbers (<tt>add-complex</tt>,
<tt>sub-complex</tt>, <tt>mul-complex</tt>, and
<tt>div-complex</tt>) in terms of generic selectors that access
parts of a complex number independent of how the number is
represented. The resulting complex-number system, as shown in
figure&nbsp;<a href="#%_fig_2.19">2.19</a>, contains two
different kinds of <a name="%_idx_2304"></a>abstraction barriers.
The ``horizontal'' abstraction barriers play the same role as the
ones in figure&nbsp;<a href="book-Z-H-14.html#%_fig_2.1">2.1</a>.
They isolate ``higher-level'' operations from ``lower-level''
representations. In addition, there is a ``vertical'' barrier
that gives us the ability to separately design and install
alternative representations.</p>
<p><a name="%_fig_2.19"></a></p>
<div align="left">
<div align="left">
<b>Figure 2.19:</b>&nbsp;&nbsp;Data-abstraction barriers in
the complex-number system.
</div>
<table width="100%">
<tr>
<td><img src="ch2-Z-G-54.gif" border="0" /></td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p>In section&nbsp;<a href="book-Z-H-18.html#%_sec_2.5">2.5</a>
we will show how to use type tags and data-directed style to
develop a generic arithmetic package. This provides procedures
(<tt>add</tt>, <tt>mul</tt>, and so on) that can be used to
manipulate all sorts of ``numbers'' and can be easily extended
when a new kind of number is needed. In section&nbsp;<a href="book-Z-H-18.html#%_sec_2.5.3">2.5.3</a>, we'll show how to use
generic arithmetic in a system that performs symbolic
algebra.</p>
<p><a name="%_sec_2.4.1"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_2.4.1">2.4.1&nbsp;&nbsp;Representations
for Complex Numbers</a></h3>
<p><a name="%_idx_2306"></a>We will develop a system that
performs arithmetic operations on complex numbers as a simple but
unrealistic example of a program that uses generic operations. We
begin by discussing two plausible representations for complex
numbers as ordered pairs: rectangular form (real part and
imaginary part) and polar form (magnitude and angle).<a href="#footnote_Temp_268" name="call_footnote_Temp_268" id="call_footnote_Temp_268"><sup><small>43</small></sup></a>
Section&nbsp;<a href="#%_sec_2.4.2">2.4.2</a> will show how both
representations can be made to coexist in a single system through
the use of type tags and generic operations.</p>
<p>Like rational numbers, complex numbers are naturally
represented as ordered pairs. The set of complex numbers can be
thought of as a two-dimensional space with two orthogonal axes,
the ``real'' axis and the ``imaginary'' axis. (See
figure&nbsp;<a href="#%_fig_2.20">2.20</a>.) From this point of
view, the complex number <em>z</em> = <em>x</em> +
<em>i</em><em>y</em> (where <em>i</em><sup>2</sup> = - 1) can be
thought of as the point in the plane whose real coordinate is
<em>x</em> and whose imaginary coordinate is <em>y</em>. Addition
of complex numbers reduces in this representation to addition of
coordinates:</p>
<div align="left"><img src="ch2-Z-G-55.gif" border="0" /></div>
<div align="left"><img src="ch2-Z-G-56.gif" border="0" /></div>
<p>When multiplying complex numbers, it is more natural to think
in terms of representing a complex number in polar form, as a
magnitude and an angle (<em>r</em> and <em>A</em> in
figure&nbsp;<a href="#%_fig_2.20">2.20</a>). The product of two
complex numbers is the vector obtained by stretching one complex
number by the length of the other and then rotating it through
the angle of the other:</p>
<div align="left"><img src="ch2-Z-G-57.gif" border="0" /></div>
<div align="left"><img src="ch2-Z-G-58.gif" border="0" /></div>
<p>Thus, there are two different representations for complex
numbers, which are appropriate for different operations. Yet,
from the viewpoint of someone writing a program that uses complex
numbers, the principle of data abstraction suggests that all the
operations for manipulating complex numbers should be available
regardless of which representation is used by the computer. For
example, it is often useful to be able to find the magnitude of a
complex number that is specified by rectangular coordinates.
Similarly, it is often useful to be able to determine the real
part of a complex number that is specified by polar
coordinates.</p>
<p><a name="%_fig_2.20"></a></p>
<div align="left">
<div align="left">
<b>Figure 2.20:</b>&nbsp;&nbsp;Complex numbers as points in
the plane.
</div>
<table width="100%">
<tr>
<td><img src="ch2-Z-G-59.gif" border="0" /></td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p>To design such a system, we can follow the same <a name="%_idx_2310"></a>data-abstraction strategy we followed in
designing the rational-number package in section&nbsp;<a href="book-Z-H-14.html#%_sec_2.1.1">2.1.1</a>. Assume that the
operations on complex numbers are implemented in terms of four
selectors: <tt>real-part</tt>, <tt>imag-part</tt>,
<tt>magnitude</tt>, and <tt>angle</tt>. Also assume that we have
two procedures for constructing complex numbers:
<tt>make-from-real-imag</tt> returns a complex number with
specified real and imaginary parts, and
<tt>make-from-mag-ang</tt> returns a complex number with
specified magnitude and angle. These procedures have the property
that, for any complex number <tt>z</tt>, both</p>
<p>
<tt>(make-from-real-imag&nbsp;(real-part&nbsp;z)&nbsp;(imag-part&nbsp;z))<br />
</tt></p>
<p>and</p>
<p>
<tt>(make-from-mag-ang&nbsp;(magnitude&nbsp;z)&nbsp;(angle&nbsp;z))<br />
</tt></p>
<p>produce complex numbers that are equal to <tt>z</tt>.</p>
<p>Using these constructors and selectors, we can implement
arithmetic on complex numbers using the ``abstract data''
specified by the constructors and selectors, just as we did for
rational numbers in section&nbsp;<a href="book-Z-H-14.html#%_sec_2.1.1">2.1.1</a>. As shown in the
formulas above, we can add and subtract complex numbers in terms
of real and imaginary parts while multiplying and dividing
complex numbers in terms of magnitudes and angles:</p>
<p><tt><a name="%_idx_2312"></a>(define&nbsp;(add-complex&nbsp;z1&nbsp;z2)<br />
&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;(imag-part&nbsp;z1)&nbsp;(imag-part&nbsp;z2))))<br />
<a name="%_idx_2314"></a>(define&nbsp;(sub-complex&nbsp;z1&nbsp;z2)<br />
&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;(imag-part&nbsp;z1)&nbsp;(imag-part&nbsp;z2))))<br />
<a name="%_idx_2316"></a>(define&nbsp;(mul-complex&nbsp;z1&nbsp;z2)<br />
&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;(angle&nbsp;z1)&nbsp;(angle&nbsp;z2))))<br />
<a name="%_idx_2318"></a>(define&nbsp;(div-complex&nbsp;z1&nbsp;z2)<br />
&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;(angle&nbsp;z1)&nbsp;(angle&nbsp;z2))))<br />
</tt></p>
<p>To complete the complex-number package, we must choose a
representation and we must implement the constructors and
selectors in terms of primitive numbers and primitive list
structure. There are two obvious ways to do this: We can
represent a complex number in ``rectangular form'' as a pair
(real part, imaginary part) or in ``polar form'' as a pair
(magnitude, angle). Which shall we choose?</p>
<p>In order to make the different choices concrete, imagine that
there are two programmers, Ben Bitdiddle and Alyssa P. Hacker,
who are independently designing representations for the
complex-number system. <a name="%_idx_2320"></a>Ben chooses to
represent complex numbers in rectangular form. With this choice,
selecting the real and imaginary parts of a complex number is
straightforward, as is constructing a complex number with given
real and imaginary parts. To find the magnitude and the angle, or
to construct a complex number with a given magnitude and angle,
he uses the trigonometric relations</p>
<div align="left"><img src="ch2-Z-G-60.gif" border="0" /></div>
<div align="left"><img src="ch2-Z-G-61.gif" border="0" /></div>
<p>which relate the real and imaginary parts (<em>x</em>,
<em>y</em>) to the magnitude and the angle (<em>r</em>,
<em>A</em>).<a href="#footnote_Temp_269" name="call_footnote_Temp_269" id="call_footnote_Temp_269"><sup><small>44</small></sup></a> Ben's
representation is therefore given by the following selectors and
constructors:</p>
<p><tt><a name="%_idx_2328"></a>(define&nbsp;(real-part&nbsp;z)&nbsp;(car&nbsp;z))<br />
<a name="%_idx_2330"></a>(define&nbsp;(imag-part&nbsp;z)&nbsp;(cdr&nbsp;z))<br />
<a name="%_idx_2332"></a>(define&nbsp;(magnitude&nbsp;z)<br />
&nbsp;&nbsp;(sqrt&nbsp;(+&nbsp;(square&nbsp;(real-part&nbsp;z))&nbsp;(square&nbsp;(imag-part&nbsp;z)))))<br />
<a name="%_idx_2334"></a>(define&nbsp;(angle&nbsp;z)<br />
&nbsp;&nbsp;(atan&nbsp;(imag-part&nbsp;z)&nbsp;(real-part&nbsp;z)))<br />
<a name="%_idx_2336"></a>(define&nbsp;(make-from-real-imag&nbsp;x&nbsp;y)&nbsp;(cons&nbsp;x&nbsp;y))<br />
<a name="%_idx_2338"></a>(define&nbsp;(make-from-mag-ang&nbsp;r&nbsp;a)&nbsp;<br />
&nbsp;&nbsp;(cons&nbsp;(*&nbsp;r&nbsp;(cos&nbsp;a))&nbsp;(*&nbsp;r&nbsp;(sin&nbsp;a))))<br />
</tt></p>
<p><a name="%_idx_2340"></a>Alyssa, in contrast, chooses to
represent complex numbers in polar form. For her, selecting the
magnitude and angle is straightforward, but she has to use the
<a name="%_idx_2342"></a>trigonometric relations to obtain the
real and imaginary parts. Alyssa's representation is:</p>
<p><tt><a name="%_idx_2344"></a>(define&nbsp;(real-part&nbsp;z)<br />
&nbsp;&nbsp;(*&nbsp;(magnitude&nbsp;z)&nbsp;(cos&nbsp;(angle&nbsp;z))))<br />
<a name="%_idx_2346"></a>(define&nbsp;(imag-part&nbsp;z)<br />
&nbsp;&nbsp;(*&nbsp;(magnitude&nbsp;z)&nbsp;(sin&nbsp;(angle&nbsp;z))))<br />
<a name="%_idx_2348"></a>(define&nbsp;(magnitude&nbsp;z)&nbsp;(car&nbsp;z))<br />
<a name="%_idx_2350"></a>(define&nbsp;(angle&nbsp;z)&nbsp;(cdr&nbsp;z))<br />
<a name="%_idx_2352"></a>(define&nbsp;(make-from-real-imag&nbsp;x&nbsp;y)&nbsp;<br />
&nbsp;&nbsp;(cons&nbsp;(sqrt&nbsp;(+&nbsp;(square&nbsp;x)&nbsp;(square&nbsp;y)))<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(atan&nbsp;y&nbsp;x)))<br />
<a name="%_idx_2354"></a>(define&nbsp;(make-from-mag-ang&nbsp;r&nbsp;a)&nbsp;(cons&nbsp;r&nbsp;a))<br />
</tt></p>
<p>The discipline of data abstraction ensures that the same
implementation of <tt>add-complex</tt>, <tt>sub-complex</tt>,
<tt>mul-complex</tt>, and <tt>div-complex</tt> will work with
either Ben's representation or Alyssa's representation.</p>
<p><a name="%_sec_2.4.2"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_2.4.2">2.4.2&nbsp;&nbsp;Tagged
data</a></h3>
<p><a name="%_idx_2356"></a><a name="%_idx_2358"></a><a name="%_idx_2360"></a> One way to view data abstraction is as an
application of the <a name="%_idx_2362"></a><a name="%_idx_2364"></a>``principle of least commitment.'' In
implementing the complex-number system in section&nbsp;<a href="#%_sec_2.4.1">2.4.1</a>, we can use either Ben's rectangular
representation or Alyssa's polar representation. The abstraction
barrier formed by the selectors and constructors permits us to
defer to the last possible moment the choice of a concrete
representation for our data objects and thus retain maximum
flexibility in our system design.</p>
<p>The principle of least commitment can be carried to even
further extremes. If we desire, we can maintain the ambiguity of
representation even <em>after</em> we have designed the selectors
and constructors, and elect to use both Ben's representation
<em>and</em> Alyssa's representation. If both representations are
included in a single system, however, we will need some way to
distinguish data in polar form from data in rectangular form.
Otherwise, if we were asked, for instance, to find the
<tt>magnitude</tt> of the pair (3,4), we wouldn't know whether to
answer 5 (interpreting the number in rectangular form) or 3
(interpreting the number in polar form). A straightforward way to
accomplish this distinction is to include a <a name="%_idx_2366"></a><em>type tag</em> -- the symbol
<tt>rectangular</tt> or <tt>polar</tt> -- as part of each complex
number. Then when we need to manipulate a complex number we can
use the tag to decide which selector to apply.</p>
<p>In order to manipulate tagged data, we will assume that we
have procedures <tt>type-tag</tt> and <tt>contents</tt> that
extract from a data object the tag and the actual contents (the
polar or rectangular coordinates, in the case of a complex
number). We will also postulate a procedure <tt>attach-tag</tt>
that takes a tag and contents and produces a tagged data object.
A straightforward way to implement this is to use ordinary list
structure:</p>
<p><tt><a name="%_idx_2368"></a>(define&nbsp;(attach-tag&nbsp;type-tag&nbsp;contents)<br />
&nbsp;&nbsp;(cons&nbsp;type-tag&nbsp;contents))<br />
<a name="%_idx_2370"></a>(define&nbsp;(type-tag&nbsp;datum)<br />
&nbsp;&nbsp;(if&nbsp;(pair?&nbsp;datum)<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(car&nbsp;datum)<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(error&nbsp;"Bad&nbsp;tagged&nbsp;datum&nbsp;--&nbsp;TYPE-TAG"&nbsp;datum)))<br />
<a name="%_idx_2372"></a>(define&nbsp;(contents&nbsp;datum)<br />
&nbsp;&nbsp;(if&nbsp;(pair?&nbsp;datum)<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(cdr&nbsp;datum)<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(error&nbsp;"Bad&nbsp;tagged&nbsp;datum&nbsp;--&nbsp;CONTENTS"&nbsp;datum)))<br />
</tt></p>
<p>Using these procedures, we can define predicates
<tt>rectangular?</tt> and <tt>polar?</tt>, which recognize polar
and rectangular numbers, respectively:</p>
<p><tt><a name="%_idx_2374"></a>(define&nbsp;(rectangular?&nbsp;z)<br />
&nbsp;&nbsp;(eq?&nbsp;(type-tag&nbsp;z)&nbsp;'rectangular))<br />
<a name="%_idx_2376"></a>(define&nbsp;(polar?&nbsp;z)<br />
&nbsp;&nbsp;(eq?&nbsp;(type-tag&nbsp;z)&nbsp;'polar))<br /></tt></p>
<p>With type tags, Ben and Alyssa can now modify their code so
that their two different representations can coexist in the same
system. Whenever Ben constructs a complex number, he tags it as
rectangular. Whenever Alyssa constructs a complex number, she
tags it as polar. In addition, Ben and Alyssa must make sure that
the names of their procedures do not conflict. One way to do this
is for Ben to append the suffix <tt>rectangular</tt> to the name
of each of his representation procedures and for Alyssa to append
<tt>polar</tt> to the names of hers. Here is Ben's revised
rectangular representation from section&nbsp;<a href="#%_sec_2.4.1">2.4.1</a>:</p>
<p><tt><a name="%_idx_2378"></a>(define&nbsp;(real-part-rectangular&nbsp;z)&nbsp;(car&nbsp;z))<br />
<a name="%_idx_2380"></a>(define&nbsp;(imag-part-rectangular&nbsp;z)&nbsp;(cdr&nbsp;z))<br />
<a name="%_idx_2382"></a>(define&nbsp;(magnitude-rectangular&nbsp;z)<br />
&nbsp;&nbsp;(sqrt&nbsp;(+&nbsp;(square&nbsp;(real-part-rectangular&nbsp;z))<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(square&nbsp;(imag-part-rectangular&nbsp;z)))))<br />
<a name="%_idx_2384"></a>(define&nbsp;(angle-rectangular&nbsp;z)<br />
&nbsp;&nbsp;(atan&nbsp;(imag-part-rectangular&nbsp;z)<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(real-part-rectangular&nbsp;z)))<br />
<a name="%_idx_2386"></a>(define&nbsp;(make-from-real-imag-rectangular&nbsp;x&nbsp;y)<br />
&nbsp;&nbsp;(attach-tag&nbsp;'rectangular&nbsp;(cons&nbsp;x&nbsp;y)))<br />
<a name="%_idx_2388"></a>(define&nbsp;(make-from-mag-ang-rectangular&nbsp;r&nbsp;a)&nbsp;<br />
&nbsp;&nbsp;(attach-tag&nbsp;'rectangular<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(cons&nbsp;(*&nbsp;r&nbsp;(cos&nbsp;a))&nbsp;(*&nbsp;r&nbsp;(sin&nbsp;a)))))<br />
</tt></p>
<p>and here is Alyssa's revised polar representation:</p>
<p><tt><a name="%_idx_2390"></a>(define&nbsp;(real-part-polar&nbsp;z)<br />
&nbsp;&nbsp;(*&nbsp;(magnitude-polar&nbsp;z)&nbsp;(cos&nbsp;(angle-polar&nbsp;z))))<br />
<a name="%_idx_2392"></a>(define&nbsp;(imag-part-polar&nbsp;z)<br />
&nbsp;&nbsp;(*&nbsp;(magnitude-polar&nbsp;z)&nbsp;(sin&nbsp;(angle-polar&nbsp;z))))<br />
<a name="%_idx_2394"></a>(define&nbsp;(magnitude-polar&nbsp;z)&nbsp;(car&nbsp;z))<br />
<a name="%_idx_2396"></a>(define&nbsp;(angle-polar&nbsp;z)&nbsp;(cdr&nbsp;z))<br />
<a name="%_idx_2398"></a>(define&nbsp;(make-from-real-imag-polar&nbsp;x&nbsp;y)&nbsp;<br />
&nbsp;&nbsp;(attach-tag&nbsp;'polar<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(cons&nbsp;(sqrt&nbsp;(+&nbsp;(square&nbsp;x)&nbsp;(square&nbsp;y)))<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(atan&nbsp;y&nbsp;x))))<br />
<a name="%_idx_2400"></a>(define&nbsp;(make-from-mag-ang-polar&nbsp;r&nbsp;a)<br />
&nbsp;&nbsp;(attach-tag&nbsp;'polar&nbsp;(cons&nbsp;r&nbsp;a)))<br />
</tt></p>
<p><a name="%_idx_2402"></a><a name="%_idx_2404"></a>Each generic
selector is implemented as a procedure that checks the tag of its
argument and calls the appropriate procedure for handling data of
that type. For example, to obtain the real part of a complex
number, <tt>real-part</tt> examines the tag to determine whether
to use Ben's <tt>real-part-rectangular</tt> or Alyssa's
<tt>real-part-polar</tt>. In either case, we use
<tt>contents</tt> to extract the bare, untagged datum and send
this to the rectangular or polar procedure as required:</p>
<p><tt><a name="%_idx_2406"></a>(define&nbsp;(real-part&nbsp;z)<br />
&nbsp;&nbsp;(cond&nbsp;((rectangular?&nbsp;z)&nbsp;<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(real-part-rectangular&nbsp;(contents&nbsp;z)))<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((polar?&nbsp;z)<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(real-part-polar&nbsp;(contents&nbsp;z)))<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else&nbsp;(error&nbsp;"Unknown&nbsp;type&nbsp;--&nbsp;REAL-PART"&nbsp;z))))<br />
<a name="%_idx_2408"></a>(define&nbsp;(imag-part&nbsp;z)<br />
&nbsp;&nbsp;(cond&nbsp;((rectangular?&nbsp;z)<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(imag-part-rectangular&nbsp;(contents&nbsp;z)))<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((polar?&nbsp;z)<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(imag-part-polar&nbsp;(contents&nbsp;z)))<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else&nbsp;(error&nbsp;"Unknown&nbsp;type&nbsp;--&nbsp;IMAG-PART"&nbsp;z))))<br />
<a name="%_idx_2410"></a>(define&nbsp;(magnitude&nbsp;z)<br />
&nbsp;&nbsp;(cond&nbsp;((rectangular?&nbsp;z)<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(magnitude-rectangular&nbsp;(contents&nbsp;z)))<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((polar?&nbsp;z)<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(magnitude-polar&nbsp;(contents&nbsp;z)))<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else&nbsp;(error&nbsp;"Unknown&nbsp;type&nbsp;--&nbsp;MAGNITUDE"&nbsp;z))))<br />
<a name="%_idx_2412"></a>(define&nbsp;(angle&nbsp;z)<br />
&nbsp;&nbsp;(cond&nbsp;((rectangular?&nbsp;z)<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(angle-rectangular&nbsp;(contents&nbsp;z)))<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((polar?&nbsp;z)<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(angle-polar&nbsp;(contents&nbsp;z)))<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else&nbsp;(error&nbsp;"Unknown&nbsp;type&nbsp;--&nbsp;ANGLE"&nbsp;z))))<br />
</tt></p>
<p>To implement the complex-number arithmetic operations, we can
use the same procedures <tt>add-complex</tt>,
<tt>sub-complex</tt>, <tt>mul-complex</tt>, and
<tt>div-complex</tt> from section&nbsp;<a href="#%_sec_2.4.1">2.4.1</a>, because the selectors they call are
generic, and so will work with either representation. For
example, the procedure <tt>add-complex</tt> is still</p>
<p><tt>(define&nbsp;(add-complex&nbsp;z1&nbsp;z2)<br />
&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;(imag-part&nbsp;z1)&nbsp;(imag-part&nbsp;z2))))<br />
</tt></p>
<p>Finally, we must choose whether to construct complex numbers
using Ben's representation or Alyssa's representation. One
reasonable choice is to construct rectangular numbers whenever we
have real and imaginary parts and to construct polar numbers
whenever we have magnitudes and angles:</p>
<p><tt><a name="%_idx_2414"></a>(define&nbsp;(make-from-real-imag&nbsp;x&nbsp;y)<br />
&nbsp;&nbsp;(make-from-real-imag-rectangular&nbsp;x&nbsp;y))<br />
<a name="%_idx_2416"></a>(define&nbsp;(make-from-mag-ang&nbsp;r&nbsp;a)<br />
&nbsp;&nbsp;(make-from-mag-ang-polar&nbsp;r&nbsp;a))<br /></tt></p>
<p><a name="%_fig_2.21"></a></p>
<div align="left">
<div align="left">
<b>Figure 2.21:</b>&nbsp;&nbsp;Structure of the generic
complex-arithmetic system.
</div>
<table width="100%">
<tr>
<td><img src="ch2-Z-G-62.gif" border="0" /></td>
</tr>
<tr>
<td><a name="%_idx_2418"></a></td>
</tr>
</table>
</div>
<p>The resulting complex-number system has the structure shown in
figure&nbsp;<a href="#%_fig_2.21">2.21</a>. The system has been
decomposed into three relatively independent parts: the
complex-number-arithmetic operations, Alyssa's polar
implementation, and Ben's rectangular implementation. The polar
and rectangular implementations could have been written by Ben
and Alyssa working separately, and both of these can be used as
underlying representations by a third programmer implementing the
complex-arithmetic procedures in terms of the abstract
constructor/selector interface.</p>
<p><a name="%_idx_2420"></a><a name="%_idx_2422"></a>Since each
data object is tagged with its type, the selectors operate on the
data in a generic manner. That is, each selector is defined to
have a behavior that depends upon the particular type of data it
is applied to. Notice the general mechanism for interfacing the
separate representations: Within a given representation
implementation (say, Alyssa's polar package) a complex number is
an untyped pair (magnitude, angle). When a generic selector
operates on a number of <tt>polar</tt> type, it strips off the
tag and passes the contents on to Alyssa's code. Conversely, when
Alyssa constructs a number for general use, she tags it with a
type so that it can be appropriately recognized by the
higher-level procedures. This discipline of stripping off and
attaching tags as data objects are passed from level to level can
be an important organizational strategy, as we shall see in
section&nbsp;<a href="book-Z-H-18.html#%_sec_2.5">2.5</a>.</p>
<p><a name="%_sec_2.4.3"></a></p>
<h3><a href="book-Z-H-4.html#%_toc_%_sec_2.4.3">2.4.3&nbsp;&nbsp;Data-Directed
Programming and Additivity</a></h3>
<p><a name="%_idx_2424"></a><a name="%_idx_2426"></a> <a name="%_idx_2428"></a>The general strategy of checking the type of a
datum and calling an appropriate procedure is called <a name="%_idx_2430"></a><a name="%_idx_2432"></a><em>dispatching on
type</em>. This is a powerful strategy for obtaining modularity
in system design. On the other hand, implementing the dispatch as
in section&nbsp;<a href="#%_sec_2.4.2">2.4.2</a> has two
significant weaknesses. One weakness is that the generic
interface procedures (<tt>real-part</tt>, <tt>imag-part</tt>,
<tt>magnitude</tt>, and <tt>angle</tt>) must know about all the
different representations. For instance, suppose we wanted to
incorporate a new representation for complex numbers into our
complex-number system. We would need to identify this new
representation with a type, and then add a clause to each of the
generic interface procedures to check for the new type and apply
the appropriate selector for that representation.</p>
<p>Another weakness of the technique is that even though the
individual representations can be designed separately, we must
guarantee that no two procedures in the entire system have the
same name. This is why Ben and Alyssa had to change the names of
their original procedures from section&nbsp;<a href="#%_sec_2.4.1">2.4.1</a>.</p>
<p>The issue underlying both of these weaknesses is that the
technique for implementing generic interfaces is not
<em>additive</em>. The person implementing the generic selector
procedures must modify those procedures each time a new
representation is installed, and the people interfacing the
individual representations must modify their code to avoid name
conflicts. In each of these cases, the changes that must be made
to the code are straightforward, but they must be made
nonetheless, and this is a source of inconvenience and error.
This is not much of a problem for the complex-number system as it
stands, but suppose there were not two but hundreds of different
representations for complex numbers. And suppose that there were
many generic selectors to be maintained in the abstract-data
interface. Suppose, in fact, that no one programmer knew all the
interface procedures or all the representations. The problem is
real and must be addressed in such programs as large-scale
data-base-management systems.</p>
<p>What we need is a means for modularizing the system design
even further. This is provided by the programming technique known
as <em>data-directed programming</em>. To understand how
data-directed programming works, begin with the observation that
whenever we deal with a set of generic operations that are common
to a set of different types we are, in effect, dealing with a
two-dimensional table that contains the possible operations on
one axis and the possible types on the other axis. The entries in
the table are the procedures that implement each operation for
each type of argument presented. In the complex-number system
developed in the previous section, the correspondence between
operation name, data type, and actual procedure was spread out
among the various conditional clauses in the generic interface
procedures. But the same information could have been organized in
a table, as shown in figure&nbsp;<a href="#%_fig_2.22">2.22</a>.</p>
<p><a name="%_idx_2434"></a>Data-directed programming is the
technique of designing programs to work with such a table
directly. Previously, we implemented the mechanism that
interfaces the complex-arithmetic code with the two
representation packages as a set of procedures that each perform
an explicit dispatch on type. Here we will implement the
interface as a single procedure that looks up the combination of
the operation name and argument type in the table to find the
correct procedure to apply, and then applies it to the contents
of the argument. If we do this, then to add a new representation
package to the system we need not change any existing procedures;
we need only add new entries to the table.</p>
<p><a name="%_fig_2.22"></a></p>
<div align="left">
<div align="left">
<b>Figure 2.22:</b>&nbsp;&nbsp;Table of operations for the
complex-number system.
</div>
<table width="100%">
<tr>
<td><img src="ch2-Z-G-63.gif" border="0" /></td>
</tr>
<tr>
<td></td>
</tr>
</table>
</div>
<p>To implement this plan, assume that we have two procedures,
<tt>put</tt> and <tt>get</tt>, for manipulating the
operation-and-type table: <a name="%_idx_2436"></a></p>
<ul>
<li>
<tt>(put &lt;<em>op</em>&gt; &lt;<em>type</em>&gt;
&lt;<em>item</em>&gt;)</tt><br />
installs the <tt>&lt;<em>item</em>&gt;</tt> in the table,
indexed by the <tt>&lt;<em>op</em>&gt;</tt> and the
<tt>&lt;<em>type</em>&gt;</tt>.
<p><a name="%_idx_2440"></a></p>
</li>
<li><tt>(get &lt;<em>op</em>&gt;
&lt;<em>type</em>&gt;)</tt><br />
looks up the <tt>&lt;<em>op</em>&gt;</tt>,
<tt>&lt;<em>type</em>&gt;</tt> entry in the table and returns
the item found there. If no item is found, <tt>get</tt> returns
false.</li>
</ul>
<p>For now, we can assume that <tt>put</tt> and <tt>get</tt> are
included in our language. In chapter&nbsp;3
(section&nbsp;<a href="book-Z-H-22.html#%_sec_3.3.3">3.3.3</a>,
exercise&nbsp;<a href="book-Z-H-22.html#%_thm_3.24">3.24</a>) we
will see how to implement these and other operations for
manipulating tables.</p>
<p>Here is how data-directed programming can be used in the
complex-number system. Ben, who developed the rectangular
representation, implements his code just as he did originally. He
defines a collection of procedures, or a <a name="%_idx_2442"></a><em>package</em>, and interfaces these to the
rest of the system by adding entries to the table that tell the
system how to operate on rectangular numbers. This is
accomplished by calling the following procedure: <a name="%_idx_2444"></a><a name="%_idx_2446"></a></p>
<p><tt><a name="%_idx_2448"></a>(define&nbsp;(install-rectangular-package)<br />
&nbsp;&nbsp;<em>;;&nbsp;internal&nbsp;procedures</em><br />
&nbsp;&nbsp;(define&nbsp;(real-part&nbsp;z)&nbsp;(car&nbsp;z))<br />
&nbsp;&nbsp;(define&nbsp;(imag-part&nbsp;z)&nbsp;(cdr&nbsp;z))<br />
&nbsp;&nbsp;(define&nbsp;(make-from-real-imag&nbsp;x&nbsp;y)&nbsp;(cons&nbsp;x&nbsp;y))<br />
&nbsp;&nbsp;(define&nbsp;(magnitude&nbsp;z)<br />
&nbsp;&nbsp;&nbsp;&nbsp;(sqrt&nbsp;(+&nbsp;(square&nbsp;(real-part&nbsp;z))<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(square&nbsp;(imag-part&nbsp;z)))))<br />
&nbsp;&nbsp;(define&nbsp;(angle&nbsp;z)<br />
&nbsp;&nbsp;&nbsp;&nbsp;(atan&nbsp;(imag-part&nbsp;z)&nbsp;(real-part&nbsp;z)))<br />
&nbsp;&nbsp;(define&nbsp;(make-from-mag-ang&nbsp;r&nbsp;a)&nbsp;<br />
&nbsp;&nbsp;&nbsp;&nbsp;(cons&nbsp;(*&nbsp;r&nbsp;(cos&nbsp;a))&nbsp;(*&nbsp;r&nbsp;(sin&nbsp;a))))<br />
&nbsp;&nbsp;<em>;;&nbsp;interface&nbsp;to&nbsp;the&nbsp;rest&nbsp;of&nbsp;the&nbsp;system</em><br />
&nbsp;&nbsp;(define&nbsp;(tag&nbsp;x)&nbsp;(attach-tag&nbsp;'rectangular&nbsp;x))<br />
&nbsp;&nbsp;(put&nbsp;'real-part&nbsp;'(rectangular)&nbsp;real-part)<br />
&nbsp;&nbsp;(put&nbsp;'imag-part&nbsp;'(rectangular)&nbsp;imag-part)<br />
&nbsp;&nbsp;(put&nbsp;'magnitude&nbsp;'(rectangular)&nbsp;magnitude)<br />
&nbsp;&nbsp;(put&nbsp;'angle&nbsp;'(rectangular)&nbsp;angle)<br />
&nbsp;&nbsp;(put&nbsp;'make-from-real-imag&nbsp;'rectangular&nbsp;<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;'rectangular&nbsp;<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>Notice that the internal procedures here are the same
procedures from section&nbsp;<a href="#%_sec_2.4.1">2.4.1</a>
that Ben wrote when he was working in isolation. No changes are
necessary in order to interface them to the rest of the system.
Moreover, since these procedure definitions are internal to the
installation procedure, Ben needn't worry about name conflicts
with other procedures outside the rectangular package. To
interface these to the rest of the system, Ben installs his
<tt>real-part</tt> procedure under the operation name
<tt>real-part</tt> and the type <tt>(rectangular)</tt>, and
similarly for the other selectors.<a href="#footnote_Temp_270" name="call_footnote_Temp_270" id="call_footnote_Temp_270"><sup><small>45</small></sup></a> The
interface also defines the constructors to be used by the
external system.<a href="#footnote_Temp_271" name="call_footnote_Temp_271" id="call_footnote_Temp_271"><sup><small>46</small></sup></a> These
are identical to Ben's internally defined constructors, except
that they attach the tag.</p>
<p><a name="%_idx_2450"></a><a name="%_idx_2452"></a>Alyssa's
polar package is analogous:</p>
<p><tt><a name="%_idx_2454"></a>(define&nbsp;(install-polar-package)<br />
&nbsp;&nbsp;<em>;;&nbsp;internal&nbsp;procedures</em><br />
&nbsp;&nbsp;(define&nbsp;(magnitude&nbsp;z)&nbsp;(car&nbsp;z))<br />
&nbsp;&nbsp;(define&nbsp;(angle&nbsp;z)&nbsp;(cdr&nbsp;z))<br />
&nbsp;&nbsp;(define&nbsp;(make-from-mag-ang&nbsp;r&nbsp;a)&nbsp;(cons&nbsp;r&nbsp;a))<br />
&nbsp;&nbsp;(define&nbsp;(real-part&nbsp;z)<br />
&nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;(magnitude&nbsp;z)&nbsp;(cos&nbsp;(angle&nbsp;z))))<br />
&nbsp;&nbsp;(define&nbsp;(imag-part&nbsp;z)<br />
&nbsp;&nbsp;&nbsp;&nbsp;(*&nbsp;(magnitude&nbsp;z)&nbsp;(sin&nbsp;(angle&nbsp;z))))<br />
&nbsp;&nbsp;(define&nbsp;(make-from-real-imag&nbsp;x&nbsp;y)&nbsp;<br />
&nbsp;&nbsp;&nbsp;&nbsp;(cons&nbsp;(sqrt&nbsp;(+&nbsp;(square&nbsp;x)&nbsp;(square&nbsp;y)))<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(atan&nbsp;y&nbsp;x)))<br />
&nbsp;&nbsp;<em>;;&nbsp;interface&nbsp;to&nbsp;the&nbsp;rest&nbsp;of&nbsp;the&nbsp;system</em><br />
&nbsp;&nbsp;(define&nbsp;(tag&nbsp;x)&nbsp;(attach-tag&nbsp;'polar&nbsp;x))<br />
&nbsp;&nbsp;(put&nbsp;'real-part&nbsp;'(polar)&nbsp;real-part)<br />
&nbsp;&nbsp;(put&nbsp;'imag-part&nbsp;'(polar)&nbsp;imag-part)<br />
&nbsp;&nbsp;(put&nbsp;'magnitude&nbsp;'(polar)&nbsp;magnitude)<br />
&nbsp;&nbsp;(put&nbsp;'angle&nbsp;'(polar)&nbsp;angle)<br />
&nbsp;&nbsp;(put&nbsp;'make-from-real-imag&nbsp;'polar<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;'polar&nbsp;<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>Even though Ben and Alyssa both still use their original
procedures defined with the same names as each other's (e.g.,
<tt>real-part</tt>), these definitions are now internal to
different procedures (see section&nbsp;<a href="book-Z-H-10.html#%_sec_1.1.8">1.1.8</a>), so there is no name
conflict.</p>
<p>The complex-arithmetic selectors access the table by means of
a general ``operation'' procedure called <tt>apply-generic</tt>,
which applies a generic operation to some arguments.
<tt>Apply-generic</tt> looks in the table under the name of the
operation and the types of the arguments and applies the
resulting procedure if one is present:<a href="#footnote_Temp_272" name="call_footnote_Temp_272" id="call_footnote_Temp_272"><sup><small>47</small></sup></a></p>
<p><tt><a name="%_idx_2462"></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;(error<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;"No&nbsp;method&nbsp;for&nbsp;these&nbsp;types&nbsp;--&nbsp;APPLY-GENERIC"<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(list&nbsp;op&nbsp;type-tags))))))<br />
</tt></p>
<p>Using <tt>apply-generic</tt>, we can define our generic
selectors as follows:</p>
<p><tt><a name="%_idx_2464"></a>(define&nbsp;(real-part&nbsp;z)&nbsp;(apply-generic&nbsp;'real-part&nbsp;z))<br />
<a name="%_idx_2466"></a>(define&nbsp;(imag-part&nbsp;z)&nbsp;(apply-generic&nbsp;'imag-part&nbsp;z))<br />
<a name="%_idx_2468"></a>(define&nbsp;(magnitude&nbsp;z)&nbsp;(apply-generic&nbsp;'magnitude&nbsp;z))<br />
<a name="%_idx_2470"></a>(define&nbsp;(angle&nbsp;z)&nbsp;(apply-generic&nbsp;'angle&nbsp;z))<br />
</tt></p>
<p>Observe that these do not change at all if a new
representation is added to the system.</p>
<p>We can also extract from the table the constructors to be used
by the programs external to the packages in making complex
numbers from real and imaginary parts and from magnitudes and
angles. As in section&nbsp;<a href="#%_sec_2.4.2">2.4.2</a>, we
construct rectangular numbers whenever we have real and imaginary
parts, and polar numbers whenever we have magnitudes and
angles:</p>
<p><tt><a name="%_idx_2472"></a>(define&nbsp;(make-from-real-imag&nbsp;x&nbsp;y)<br />
&nbsp;&nbsp;((get&nbsp;'make-from-real-imag&nbsp;'rectangular)&nbsp;x&nbsp;y))<br />
<a name="%_idx_2474"></a>(define&nbsp;(make-from-mag-ang&nbsp;r&nbsp;a)<br />
&nbsp;&nbsp;((get&nbsp;'make-from-mag-ang&nbsp;'polar)&nbsp;r&nbsp;a))<br />
</tt></p>
<p><a name="%_thm_2.73"></a> <b>Exercise
2.73.</b>&nbsp;&nbsp;Section&nbsp;<a href="book-Z-H-16.html#%_sec_2.3.2">2.3.2</a> described a program that
performs symbolic differentiation: <a name="%_idx_2476"></a><a name="%_idx_2478"></a></p>
<p><tt>(define&nbsp;(deriv&nbsp;exp&nbsp;var)<br />
&nbsp;&nbsp;(cond&nbsp;((number?&nbsp;exp)&nbsp;0)<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((variable?&nbsp;exp)&nbsp;(if&nbsp;(same-variable?&nbsp;exp&nbsp;var)&nbsp;1&nbsp;0))<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((sum?&nbsp;exp)<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(make-sum&nbsp;(deriv&nbsp;(addend&nbsp;exp)&nbsp;var)<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(deriv&nbsp;(augend&nbsp;exp)&nbsp;var)))<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((product?&nbsp;exp)<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(make-sum<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(make-product&nbsp;(multiplier&nbsp;exp)<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;(deriv&nbsp;(multiplicand&nbsp;exp)&nbsp;var))<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(make-product&nbsp;(deriv&nbsp;(multiplier&nbsp;exp)&nbsp;var)<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;(multiplicand&nbsp;exp))))<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&lt;<em>more&nbsp;rules&nbsp;can&nbsp;be&nbsp;added&nbsp;here</em>&gt;<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else&nbsp;(error&nbsp;"unknown&nbsp;expression&nbsp;type&nbsp;--&nbsp;DERIV"&nbsp;exp))))<br />
</tt></p>
<p>We can regard this program as performing a dispatch on the
type of the expression to be differentiated. In this situation
the ``type tag'' of the datum is the algebraic operator symbol
(such as <tt>+</tt>) and the operation being performed is
<tt>deriv</tt>. We can transform this program into data-directed
style by rewriting the basic derivative procedure as</p>
<p><tt><a name="%_idx_2480"></a>(define&nbsp;(deriv&nbsp;exp&nbsp;var)<br />
&nbsp;&nbsp;&nbsp;(cond&nbsp;((number?&nbsp;exp)&nbsp;0)<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((variable?&nbsp;exp)&nbsp;(if&nbsp;(same-variable?&nbsp;exp&nbsp;var)&nbsp;1&nbsp;0))<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else&nbsp;((get&nbsp;'deriv&nbsp;(operator&nbsp;exp))&nbsp;(operands&nbsp;exp)<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;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;var))))<br />
(define&nbsp;(operator&nbsp;exp)&nbsp;(car&nbsp;exp))<br />
(define&nbsp;(operands&nbsp;exp)&nbsp;(cdr&nbsp;exp))<br /></tt></p>
<p>a.&nbsp;&nbsp;Explain what was done above. Why can't we
assimilate the predicates <tt>number?</tt> and
<tt>same-variable?</tt> into the data-directed dispatch?</p>
<p>b.&nbsp;&nbsp;Write the procedures for derivatives of sums and
products, and the auxiliary code required to install them in the
table used by the program above.</p>
<p>c.&nbsp;&nbsp;Choose any additional differentiation rule that
you like, such as the one for exponents (exercise&nbsp;<a href="book-Z-H-16.html#%_thm_2.56">2.56</a>), and install it in this
data-directed system.</p>
<p>d.&nbsp;&nbsp;In this simple algebraic manipulator the type of
an expression is the algebraic operator that binds it together.
Suppose, however, we indexed the procedures in the opposite way,
so that the dispatch line in <tt>deriv</tt> looked like</p>
<p>
<tt>((get&nbsp;(operator&nbsp;exp)&nbsp;'deriv)&nbsp;(operands&nbsp;exp)&nbsp;var)<br />
</tt></p>
<p>What corresponding changes to the derivative system are
required?</p>
<p><a name="%_thm_2.74"></a> <b>Exercise
2.74.</b>&nbsp;&nbsp;<a name="%_idx_2482"></a><a name="%_idx_2484"></a>Insatiable Enterprises, Inc., is a highly
decentralized conglomerate company consisting of a large number
of independent divisions located all over the world. The
company's computer facilities have just been interconnected by
means of a clever network-interfacing scheme that makes the
entire network appear to any user to be a single computer.
Insatiable's president, in her first attempt to exploit the
ability of the network to extract administrative information from
division files, is dismayed to discover that, although all the
division files have been implemented as data structures in
Scheme, the particular data structure used varies from division
to division. A meeting of division managers is hastily called to
search for a strategy to integrate the files that will satisfy
headquarters' needs while preserving the existing autonomy of the
divisions.</p>
<p>Show how such a strategy can be implemented with data-directed
programming. As an example, suppose that each division's
personnel records consist of a single file, which contains a set
of records keyed on employees' names. The structure of the set
varies from division to division. Furthermore, each employee's
record is itself a set (structured differently from division to
division) that contains information keyed under identifiers such
as <tt>address</tt> and <tt>salary</tt>. In particular:</p>
<p>a.&nbsp;&nbsp;Implement for headquarters a <tt>get-record</tt>
procedure that retrieves a specified employee's record from a
specified personnel file. The procedure should be applicable to
any division's file. Explain how the individual divisions' files
should be structured. In particular, what type information must
be supplied?</p>
<p>b.&nbsp;&nbsp;Implement for headquarters a <tt>get-salary</tt>
procedure that returns the salary information from a given
employee's record from any division's personnel file. How should
the record be structured in order to make this operation
work?</p>
<p>c.&nbsp;&nbsp;Implement for headquarters a
<tt>find-employee-record</tt> procedure. This should search all
the divisions' files for the record of a given employee and
return the record. Assume that this procedure takes as arguments
an employee's name and a list of all the divisions' files.</p>
<p>d.&nbsp;&nbsp;When Insatiable takes over a new company, what
changes must be made in order to incorporate the new personnel
information into the central system?</p>
<p><a name="%_sec_Temp_275"></a></p>
<h4><a href="book-Z-H-4.html#%_toc_%_sec_Temp_275">Message
passing</a></h4>
<p><a name="%_idx_2486"></a> The key idea of data-directed
programming is to handle generic operations in programs by
dealing explicitly with operation-and-type tables, such as the
table in figure&nbsp;<a href="#%_fig_2.22">2.22</a>. The style of
programming we used in section&nbsp;<a href="#%_sec_2.4.2">2.4.2</a> organized the required dispatching on
type by having each operation take care of its own dispatching.
In effect, this decomposes the operation-and-type table into
rows, with each generic operation procedure representing a row of
the table.</p>
<p>An alternative implementation strategy is to decompose the
table into columns and, instead of using ``intelligent
operations'' that dispatch on data types, to work with
``intelligent data objects'' that dispatch on operation names. We
can do this by arranging things so that a data object, such as a
rectangular number, is represented as a procedure that takes as
input the required operation name and performs the operation
indicated. In such a discipline, <tt>make-from-real-imag</tt>
could be written as</p>
<p><tt><a name="%_idx_2488"></a>(define&nbsp;(make-from-real-imag&nbsp;x&nbsp;y)<br />
&nbsp;&nbsp;(define&nbsp;(dispatch&nbsp;op)<br />
&nbsp;&nbsp;&nbsp;&nbsp;(cond&nbsp;((eq?&nbsp;op&nbsp;'real-part)&nbsp;x)<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((eq?&nbsp;op&nbsp;'imag-part)&nbsp;y)<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((eq?&nbsp;op&nbsp;'magnitude)<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(sqrt&nbsp;(+&nbsp;(square&nbsp;x)&nbsp;(square&nbsp;y))))<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;((eq?&nbsp;op&nbsp;'angle)&nbsp;(atan&nbsp;y&nbsp;x))<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(else<br />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(error&nbsp;"Unknown&nbsp;op&nbsp;--&nbsp;MAKE-FROM-REAL-IMAG"&nbsp;op))))<br />
&nbsp;&nbsp;dispatch)<br /></tt></p>
<p>The corresponding <tt>apply-generic</tt> procedure, which
applies a generic operation to an argument, now simply feeds the
operation's name to the data object and lets the object do the
work:<a href="#footnote_Temp_276" name="call_footnote_Temp_276" id="call_footnote_Temp_276"><sup><small>48</small></sup></a></p>
<p><tt><a name="%_idx_2490"></a>(define&nbsp;(apply-generic&nbsp;op&nbsp;arg)&nbsp;(arg&nbsp;op))<br />
</tt></p>
<p>Note that the value returned by <tt>make-from-real-imag</tt>
is a procedure -- the internal <tt>dispatch</tt> procedure. This
is the procedure that is invoked when <tt>apply-generic</tt>
requests an operation to be performed.</p>
<p>This style of programming is called <em>message passing</em>.
The name comes from the image that a data object is an entity
that receives the requested operation name as a ``message.'' We
have already seen an example of message passing in
section&nbsp;<a href="book-Z-H-14.html#%_sec_2.1.3">2.1.3</a>,
where we saw how <tt>cons</tt>, <tt>car</tt>, and <tt>cdr</tt>
could be defined with no data objects but only procedures. Here
we see that message passing is not a mathematical trick but a
useful technique for organizing systems with generic operations.
In the remainder of this chapter we will continue to use
data-directed programming, rather than message passing, to
discuss generic arithmetic operations. In chapter&nbsp;3 we will
return to message passing, and we will see that it can be a
powerful tool for structuring simulation programs.</p>
<p><a name="%_thm_2.75"></a> <b>Exercise
2.75.</b>&nbsp;&nbsp;<a name="%_idx_2492"></a>Implement the
constructor <tt>make-from-mag-ang</tt> in message-passing style.
This procedure should be analogous to the
<tt>make-from-real-imag</tt> procedure given above.</p>
<p><a name="%_thm_2.76"></a> <b>Exercise
2.76.</b>&nbsp;&nbsp;<a name="%_idx_2494"></a>As a large system
with generic operations evolves, new types of data objects or new
operations may be needed. For each of the three strategies --
generic operations with explicit dispatch, data-directed style,
and message-passing-style -- describe the changes that must be
made to a system in order to add new types or new operations.
Which organization would be most appropriate for a system in
which new types must often be added? Which would be most
appropriate for a system in which new operations must often be
added?</p>
<div class="smallprint">
<hr />
</div>
<div class="footnote">
<p><a href="#call_footnote_Temp_268" name="footnote_Temp_268" id="footnote_Temp_268"><sup><small>43</small></sup></a> In
actual computational systems, rectangular form is preferable to
polar form most of the time because of <a name="%_idx_2308"></a>roundoff errors in conversion between
rectangular and polar form. This is why the complex-number
example is unrealistic. Nevertheless, it provides a clear
illustration of the design of a system using generic operations
and a good introduction to the more substantial systems to be
developed later in this chapter.</p>
<p><a href="#call_footnote_Temp_269" name="footnote_Temp_269" id="footnote_Temp_269"><sup><small>44</small></sup></a> The
arctangent function referred to <a name="%_idx_2322"></a><a name="%_idx_2324"></a><a name="%_idx_2326"></a>here, computed by Scheme's <tt>atan</tt>
procedure, is defined so as to take two arguments
<em>y</em>&nbsp;and <em>x</em> and to return the angle whose
tangent is <em>y</em>/<em>x</em>. The signs of the arguments
determine the quadrant of the angle.</p>
<p><a href="#call_footnote_Temp_270" name="footnote_Temp_270" id="footnote_Temp_270"><sup><small>45</small></sup></a> We use
the list <tt>(rectangular)</tt> rather than the symbol
<tt>rectangular</tt> to allow for the possibility of operations
with multiple arguments, not all of the same type.</p>
<p><a href="#call_footnote_Temp_271" name="footnote_Temp_271" id="footnote_Temp_271"><sup><small>46</small></sup></a> The
type the constructors are installed under needn't be a list
because a constructor is always used to make an object of one
particular type.</p>
<p><a href="#call_footnote_Temp_272" name="footnote_Temp_272" id="footnote_Temp_272"><sup><small>47</small></sup></a>
<tt>Apply-generic</tt> uses the <a name="%_idx_2456"></a>dotted-tail notation described in
exercise&nbsp;<a href="book-Z-H-15.html#%_thm_2.20">2.20</a>,
because different generic operations may take different numbers
of arguments. In <tt>apply-generic</tt>, <tt>op</tt> has as its
value the first argument to <tt>apply-generic</tt> and
<tt>args</tt> has as its value a list of the remaining
arguments.</p>
<p><tt>Apply-generic</tt> also uses the primitive procedure
<a name="%_idx_2458"></a><a name="%_idx_2460"></a><tt>apply</tt>, which takes two arguments, a
procedure and a list. <tt>Apply</tt> applies the procedure,
using the elements in the list as arguments. For example,</p>
<p>
<tt>(apply&nbsp;+&nbsp;(list&nbsp;1&nbsp;2&nbsp;3&nbsp;4))<br /></tt></p>
<p>returns 10.</p>
<p><a href="#call_footnote_Temp_276" name="footnote_Temp_276" id="footnote_Temp_276"><sup><small>48</small></sup></a> One
limitation of this organization is it permits only generic
procedures of one argument.</p>
</div>
</body>
</html>
Jump to Line
Something went wrong with that request. Please try again.