Structure and Interpretation of Computer Programs (37 page)

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
polar
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 
2.5
.

The general strategy of checking the type of a datum and calling an
appropriate procedure is called
dispatching on 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 (
real-part
,
imag-part
,
magnitude
, and
angle
) 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 issue 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 or all the representations. The problem is real and must
be addressed in such programs as large-scale data-base-management
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 procedures. But the same information could
have been organized in a table, as shown in
figure 
2.22
.

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.

Figure 2.22:
  Table of operations for the complex-number system.

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 the
  <
  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 false.
  

For now, we can assume that
put
and
get
are
included in our language. In chapter 3
(section 
3.3.3
, exercise 
3.24
)
we will see how to implement 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.
⁴⁵
The interface also defines
the constructors to be used by the external system.
⁴⁶
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
defined with the same names as each other's (e.g.,
real-part
), these
definitions are now internal to different procedures (see
section 
1.1.8
), so there is no 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))))))

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 magnitudes 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))

Exercise 2.73.
  Section 
2.3.2
described a program that
performs symbolic differentiation:

(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp) (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
           (make-product (multiplier exp)
                         (deriv (multiplicand exp) var))
           (make-product (deriv (multiplier exp) var)
                         (multiplicand exp))))
        <
more rules can be added here
>
        (else (error "unknown expression type -- DERIV" exp))))

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
+
) and the
operation being performed is
deriv
. We can transform this
program into data-directed style by rewriting the basic derivative
procedure as

(define (deriv exp var)
   (cond ((number? exp) 0)
         ((variable? exp) (if (same-variable? exp var) 1 0))
         (else ((get 'deriv (operator exp)) (operands exp)
                                            var))))
(define (operator exp) (car exp))
(define (operands exp) (cdr exp))

a.  Explain what was done above.
Why can't we assimilate the predicates
number?
and
same-variable?
into the data-directed dispatch?

b.  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.

c.  Choose any additional differentiation rule that you like, such as
the one for exponents (exercise 
2.56
),
and install it in this data-directed system.