We have introduced data abstraction, a methods 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 2.1.1 how to separate the task of designing a program that uses rational numbers from the task of implementing ration numbers in terms of computer language’s primitive mechanisms for constructing compund data. The key idea was to errect an abstraction barrier – in this case, the selectors and constructors for rational numbers – 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 precedures that perform rational arithmetic from the “higher-level” procedures that use rational numbers.
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.
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.
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 additively, that is, without having to redesign or reimplement these modules.
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 generic procedures – 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 type tags, that is, data objects that include explicit information about how they are to be processed. We will also discuss data-directed programming, a powerful and convenient implementation strategy for additively assembling systems with generic operations.
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
nothion of an abstract “complex-number” data object. We will
accomplish this by defining arithmetic procedures for complex numbers
(add-comple, sub-complex, mul-complex, and div-complex) in
terms of generic selectors that access parts of a complex number
independent of how the number is represented. The resulting
complex-numner system, as shown in the figure below, contains two
different kinds of abstraction barriers. The “horizontal” abstraction
barriers isolate “higher-level” operations from “lower-level”
representations. In addition, there is a “vertical” barrier that
gives is the ability to separately design and install alternative
representations.
In Section 2.5
we will show how to use type tags and data-directed style to develop a
generic arithmetic package. This provides procedures (add, mul,
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 2.5.3,
we’ll show how to use generic arithmetic in a system that performs
symbolic algebra.
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 and imaginary parts) and polar form (magnitude and angle). [In actual computational systems, rectangular form is preferable to polar form most of the time because of roundoff errors in conversion between rectangular and polar form. This is why the complex-number example is unrealistic. Nevertheless, is 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.] Section 2.4.2 will show how both representations can be made to coexist in a single system through the use of type tags and generic operations.
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. From this point of view, the complex number $z = x + iy$ (where $i^2 = -1$) can be thought of as the point in the plane whose real coordinate is $x$ and whose imaginary coordinate is $y$. Addition of complex numbers reduces in this representation to addition of coordinates:
When multiplying complex numbers, it is more natural to think in terms of representing a complex number in polar form, as a magniture and an angle. 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:
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 determine the real part of a complex number that is specified by polar coordinates.
To design such a system, we can follow the same data abstraction
strategy we followed in designing the rational-number package. Assume
that the operations on complex numbers are implemented in terms of
four selectors: real-part, imag-part, magnitude and angle.
Also assume that we have two procedures for constructing complex
numbers: make-from-real-imag returns a complex number with specified
real and imaginary parts, and make-from-mag-ang returns a complex
number with specified magnitude and angle. These procedures have the
property that, for any complex number z, both
(make-from-real-imag (real-part z) (imag-part z))and
(make-from-mag-ang (magnitude z) (angle z))produce complex numbers that are equal to z.
Using these constuctors and selectors, we can implement arithmetic on complex numbers using the “abstract data” specified by the constuctors and selectors. 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:
(define (add-complex z1 z2)
(make-from-real-imag (+ (real-part z1) (real-part z2))
(+ (imag-part z1) (imag-part z2))))
(define (sub-complex z1 z2)
(make-from-real-imag (- (real-part z1) (real-part z2))
(- (imag-part z1) (imag-part z2))))
(define (mul-complex z1 z2)
(make-from-real-imag (* (magnitude z1) (magnitude z2))
(+ (angle z1) (angle z2))))
(define (div-complex z1 z2)
(make-from-real-imag (/ (magnitude z1) (magnitude z2))
(- (angle z1) (angle z2))))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 or in “polar form” as a pair.
In order to make the different choices concrete, imagine that there are two programmers, Bem Bitdiddle and Alyssa P. Hacker, who are independently designing representations for the complex-number system. 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 trigonometic relations
[The arctangent function referred to here, computed by Scheme’s atan
procedure, is defined so as tp take two arguments $y$ and $x$ and to
return the angle whose tangent is $y/x$.]
which relate the real and imaginary parts to the magnitude and angle. Ben’s representation is therefore given by the following selectors and constructors:
(define (real-part z) (car z))
(define (imag-part z) (cdr z))
(define (magnitude z)
(sqrt (+ (square (real-part z)) (square (imag-part z)))))
(define (angle z)
(atan (imag-part z) (real-part z)))
(define (make-from-real-imag x y) (cons x y))
(define (make-from-mag-ang r a)
(cons (* r (cos a)) (* r (sin 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 tigonometric relations to obtain the real and imaginary parts. Alyssa’s representation is:
(define (real-part z)
(* (magnitude z) (cos (angle z))))
(define (imag-part z)
(* (magnitude z) (sin (angle z))))
(define (magnitude z) (car z))
(define (angle z) (cdr z))
(define (make-from-real-imag x y)
(cons (sqrt (+ (square x) (square y)))
(atan y x)))
(define (make-from-mag-ang r a) (cons r a))The discipline of data abstraction ensures that the same implementation of the arithmetic operations will work with either Ben’s representation or Alyssa’s representation.
One way to view data abstraction is as an application of the “principle of least commitment.” In implementing the complex-number system in Section 2.4.1, we can use either Ben’s rectangular representation or Alyssa’s polar representation. The abstraction barrier formed by the selectors and constructors premits 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.
The princple of least commitment can be carried to even further
extremes. If we desire, we can maintain the ambiguity of
representation even after we have designed the selectors and
constructors, and elect to use both Ben’s and Alyssa’s representation.
If both representations are included in a single system, however, we
will need some way to distinguish data in polar form and from data in
rectangular form. A straightforward way to accomplish this distinction
is to include a type tag – the symbol rectangular or polar –
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.
In order to manipulate tagged data, we will assume that we have
procedures type-tag and contents that extract from a data object
the tag and the acutal contents. We will also postulate a procedure
attach-tag that takes a tag and contents and produces a tagged data
object. A straightforward way to implement this is to use ordinary
list structure:
(define (attach-tag type-tag contents)
(cons type-tag contents))
(define (type-tag datum)
(if (pair? datum)
(car datum)
(error "Bad tagged datum - TYPE-TAG" datum)))
(define (contents datum)
(if (pair? datum)
(cdr datum)
(error "Bad tagged datum - CONTENTS" datum)))Using these proceudres, we can define predicates rectangular? and
polar?, which recognize retangular and polar numbers, respectively:
(define (retangular? z)
(eq? (type-tag z) 'rectangular))
(define (polar? z)
(eq? (type-tag z) 'polar))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 addtion,
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
rectangular to the name of each of his representation procedures
and for Alyssa to append polar to the names of hers. Here is Ben’s
revised rectangular representation:
(define (real-part-rectangular z) (car z))
(define (imag-part-rectangular z) (cdr z))
(define (magnitude-rectangular z)
(sqrt (+ (square (real-part-rectangular z))
(square (imag-part-rectangular z)))))
(define (angle-rectangular z)
(atan (imag-part-rectangular z)
(real-part-rectangular z)))
(define (make-from-real-imag-rectangular x y)
(attach-tag 'rectangular (cons x y)))
(define (make-from-mag-ang-rectangular r a)
(attach-tag 'rectangular
(cons (* r (cos a)) (* r (sin a)))))and here is Alyssa’s revised polar representation:
(define (real-part-polar z)
(* (magnitude-polar z) (cos (angle-polar z))))
(define (imag-part-polar z)
(* (magnitude-polar z) (sin (angle-polar z))))
(define (magnitude-polar z) (car z))
(define (angle-polar z) (cdr z))
(define (make-from-real-imag-polar x y)
(attach-tag 'polar
(cons (sqrt (+ (square x) (square y)))
(atan y x))))
(define (make-from-mag-ang-polar r a)
(attach-tag 'polar (cons r 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, real-part examines the tag to determine whether to us Ben’s
real-part-rectangular or Alyssa’s real-part-polar. In either case,
we use contents to extract the bare, untagged datum and send this to
the rectangular or polar procedure as required:
(define (real-part z)
(cond ((rectangular? z)
(real-part-rectangular (contents z)))
((polar? z)
(real-part-polar (contents z)))
(else (error "Unknown type - REAL-PART" z))))
(define (imag-part z)
(cond ((rectangular? z)
(imag-part-rectangular (contents z)))
((polar? z)
(imag-part-polar (contents z)))
(else (error "Unknown type - IMAG-PART" z))))
(define (magnitude z)
(cond ((rectangular? z)
(magnitude-rectangular (contents z)))
((polar? z)
(magnitude-polar (contents z)))
(else (error "Unknown type - MAGNITUDE" z))))
(define (angle z)
(cond ((rectangular? z)
(angle-rectangular (contents z)))
((polar? z)
(angle-polar (contents z)))
(else (error "Unknown type - ANGLE" z))))To implement the complex-arithmetic operations, we can use the same procedures, because the selectors they call are generic, and so will work with either representation.
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:
(define (make-from-real-imag x y)
(make-from-real-imag-rectangular x y))
(define (make-from-mag-ang r a)
(make-from-mag-ang-polar r a))The resulting complex-number system has been decomposed into three relatively independent parts: the complex-number-arithmetic operations, Alyssa’s polar implementation, and Ben’s rectangluar implementation. The polar and rectangular implementations could have been written by Ben and Alyssa working separately, and both of these can bu used as underlysing representations by a thrid programmer implementing the complex-arithmetic procedures in terms of the abstract constructor/selector interface.
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 behaviour 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 polar type,
it strips off the tag and passed 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
attatching tags as data objects are passed from level to level can be
an important organization strategy, as we shall see in
Section 2.5
The general strategy of checking the type of a datum and calling an appropriate procedure is called dispatching on a type. This is a powerful strategy for obtaining modularity in system design. On the other hand, implementing the dispatch as in Section 2.4.2 has two significant weaknesses. One weakness is that the generic interface procedures 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.
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 2.4.1.
The issure underlying both of these weaknesses is that the technique for implementing generic interfaces is not additive. 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 of all the representations. The problem is real and must be addressed in such programs as large-scale data-base-managements systems.
What we need is a means for modularizing the system design even further. This is provided by the programming technique known as data-directed programming. 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 proceures. But the same information could be organized in a table:
| Polar | Rectangular
-----------------------------------------------------
real-part | real-part-polar | real-part-rectangular
imag-part | imag-part-polar | imag-part-rectangular
magnitude | magnitude-polar | magnitude-rectangular
angle | angle-polar | angle-rectangular
To implement this plan, assume that we have two procedures, put and
get, for manipulating the operation-and-type-table:
(put <op> <type> <item>) installs the <item> in the table,
indexed by the <op> and <type>(get <op> <type>) looks up the <op>, <type> entry in the table
and returns the item found there. If no item is found, get returns
falseFor now, we can assume that put and get are included in our
language. In
Chapter 3 (Section 3.3.3)
we will see how to implememt these and other operations for
manipulating tables.
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 package, 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:
(define (install-rectangular-package)
;; internal procedures
(define (real-part z) (car z))
(define (imag-part z) (cdr z))
(define (make-from-real-imag x y) (cons x y))
(define (magnitude z)
(sqrt (+ (square (real-part z))
(square (imag-part z)))))
(define (angle z)
(atan (imag-part z) (real-part z)))
(define (make-from-mag-ang r a)
(cons (* r (cos a)) (* r (sin a))))
;; interface to the rest of the system
(define (tag x) (attach-tag 'rectangular x))
(put 'real-part '(rectangular) real-part)
(put 'imag-part '(rectangular) imag-part)
(put 'magnitude '(rectangular) magnitude)
(put 'angle '(rectangular) angle)
(put 'make-from-real-imag 'rectangular
(lambda (x y) (tag (make-from-real-imag x y))))
(put 'make-from-mag-ang 'rectangular
(lambda (r a) (tag (make-from-mag-ang r a))))
'done)Notice that the internal procedures here are the same procedures from
Section 2.4.1 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 real-part
procedure under the operation name real-part and the type
(rectangular), and similarly for the other selectors. [We use the
list (rectangular) rather than the symbol rectangular to allow for
the possibility of operations with multiple arguments, not all of the
same type.] The interface also defines the constructors to be used by
the external system. [The type the constructors are installed under
needn’t be a list because a constructor is always used to make an
objects of one particular type.] These are identical to Ben’s
internally defined constructors, except that they attach the tag.
Alyssa’s polar package is analogous:
(define (install-polar-package)
;; internal procedures
(define (magnitude z) (car z))
(define (angle z) (cdr z))
(define (make-from-mag-ang r a) (cons r a))
(define (real-part z)
(* (magnitude z) (cos (angle z))))
(define (imag-part z)
(* (magnitude z) (sin (angle z))))
(define (make-from-real-imag x y)
(cons (sqrt (+ (square x) (square y)))
(atan y x)))
;; interface to the rest of the system
(define (tag x) (attach-tag 'polar x))
(put 'real-part '(polar) real-part)
(put 'imag-part '(polar) imag-part)
(put 'magnitude '(polar) magnitude)
(put 'angle '(polar) angle)
(put 'make-from-real-imag 'polar
(lambda (x y) (tag (make-from-real-imag x y))))
(put 'make-from-mag-ang 'polar
(lambda (r a) (tag (make-from-mag-ang r a))))
'done)Even though Ben and Alyssa both still use their original procedures define with the same names as each other’s, these definitions are now internal to different procedures, so there is not name conflict.
The complex-arithmetic selectors access the table by means of a
general “operation” procedure called apply-generic, which applies a
generic operation to some arguments. Apply-generic 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:
(define (apply-generic op . args)
(let ((type-tags (map type-tag args)))
(let ((proc (get op type-tags)))
(if proc
(apply proc (map contents args))
(error
"No method for these types - APPLY-GENERIC"
(list op type-tags))))))[Apply-generic uses the dotted-tail notation, because different
generic operations may take different numbers of arguments. In
apply-generic, op has as its value the first argument to
apply-generic and args has as its value a list of the remaining
arguments.
Apply-generics also uses the primitive procedure apply, which
takes two arguments, a procedure and a list. Apply applies the
procedure, using the elements in the list as arguments. For example,
(apply + (list 1 2 3 4)) returns 10.]
Using apply-generic, we can define our generic selectors as follows:
(define (real-part z) (apply-generic 'real-part z))
(define (imag-part z) (apply-generic 'imag-part z))
(define (magnitude z) (apply-generic 'magnitude z))
(define (angle z) (apply-generic 'angle z))Observe that these do not change at all if a new representation is added to the system.
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 2.4.2, we construct rectangular numbers whenever we have real and imaginary parts, and polar numbers whenever we have magnitude and angles:
(define (make-from-real-imag x y)
((get 'make-from-real-imag 'rectangular) x y))
(define (make-from-mag-ang r a)
((get 'make-from-mag-ang 'polar) r a))