Structure and Interpretation of Computer Programs (36 page)

(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 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 
2.1.1
. 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-mag-ang (* (magnitude z1) (magnitude z2))
                     (+ (angle z1) (angle z2))))
(define (div-complex z1 z2)
  (make-from-mag-ang (/ (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 (real part, imaginary part)
or in “polar form” as a pair (magnitude, angle). Which shall we
choose?

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

which relate the real and imaginary parts (
x
,
y
) to the magnitude
and the angle (
r
,
A
).
⁴⁴
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
trigonometric 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
add-complex
,
sub-complex
,
mul-complex
, and
div-complex
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 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.

The principle 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 representation
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 from data in rectangular form. Otherwise, if we were
asked, for instance, to find the
magnitude
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
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 actual
contents (the polar or rectangular coordinates, in the case of a
complex number). 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 procedures, we can define predicates
rectangular?
and
polar?
, which recognize polar and rectangular numbers,
respectively:

(define (rectangular? 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 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
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 from
section 
2.4.1
:

(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 use
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-number arithmetic operations, we can use the
same procedures
add-complex
,
sub-complex
,
mul-complex
, and
div-complex
from
section 
2.4.1
, because the
selectors they call are generic, and so will work with either
representation. For example, the procedure
add-complex
is still

(define (add-complex z1 z2)
  (make-from-real-imag (+ (real-part z1) (real-part z2))
                       (+ (imag-part z1) (imag-part z2))))

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

Figure 2.21:
  Structure of the generic complex-arithmetic system.

The resulting complex-number system has the structure shown in
figure 
2.21
. 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.