2.4.2 Tagged data - SICP Comparison Edition

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 string "rectangular" or polar—as "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 functions type-tag 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 function attach-tag 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:

Original	JavaScript
`(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)))`	`function attach_tag(type_tag, contents) { return pair(type_tag, contents); } function type_tag(datum) { return is_pair(datum) ? head(datum) : error(datum, "bad tagged datum -- type_tag"); } function contents(datum) { return is_pair(datum) ? tail(datum) : error(datum, "bad tagged datum -- contents"); }`

Using these procedures, Using type_tag, we can define predicates rectangular? is_rectangular and polar?, is_polar, which recognize rectangular and polar numbers, respectively:

Original	JavaScript
`(define (rectangular? z) (eq? (type-tag z) 'rectangular)) (define (polar? z) (eq? (type-tag z) 'polar))`	`function is_rectangular(z) { return type_tag(z) === "rectangular"; } function is_polar(z) { return 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 functions 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 functions and for Alyssa to append polar to the names of hers. Here is Ben's revised rectangular representation from section 2.4.1:

Original

JavaScript

(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:

Original

JavaScript

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

function real_part_polar(z) { return magnitude_polar(z) * math_cos(angle_polar(z)); } function imag_part_polar(z) { return magnitude_polar(z) * math_sin(angle_polar(z)); } function magnitude_polar(z) { return head(z); } function angle_polar(z) { return tail(z); } function make_from_real_imag_polar(x, y) { return attach_tag("polar", pair(math_sqrt(square(x) + square(y)), math_atan2(y, x))); } function make_from_mag_ang_polar(r, a) { return attach_tag("polar", pair(r, a)); }

Each generic selector is implemented as a procedure function that checks the tag of its argument and calls the appropriate procedure function for handling data of that type. For example, to obtain the real part of a complex number, real-part real_part examines the tag to determine whether to use Ben's real-part-rectangular real_part_rectangular or Alyssa's real-part-polar. real_part_polar. In either case, we use contents to extract the bare, untagged datum and send this to the rectangular or polar procedure function as required:

Original

JavaScript

(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 functions add-complex, add_complex, sub-complex, sub_complex, mul-complex, mul_complex, and div-complex 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 function add-complex add_complex is still

Original	JavaScript
`(define (add-complex z1 z2) (make-from-real-imag (+ (real-part z1) (real-part z2)) (+ (imag-part z1) (imag-part z2))))`	`function add_complex(z1, z2) { return 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:

Original	JavaScript
`(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))`	`function make_from_real_imag(x, y) { return make_from_real_imag_rectangular(x, y); } function make_from_mag_ang(r, a) { return make_from_mag_ang_polar(r, a); }`

Original		JavaScript
Figure 2.31 Structure of the generic complex-arithmetic system.		Figure 2.32 Structure of the generic complex-arithmetic system.

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