2.5.1 Generic Arithmetic Operations - SICP Comparison Edition

The task of designing generic arithmetic operations is analogous to that of designing the generic complex-number operations. We would like, for instance, to have a generic addition procedure function add that acts like ordinary primitive addition + on ordinary numbers, like add-rat add_rat on rational numbers, and like add-complex add_complex on complex numbers. We can implement add, and the other generic arithmetic operations, by following the same strategy we used in section 2.4.3 to implement the generic selectors for complex numbers. We will attach a type tag to each kind of number and cause the generic procedure function to dispatch to an appropriate package according to the data type of its arguments.

The generic arithmetic procedures functions are defined as follows:

Original	JavaScript
`(define (add x y) (apply-generic 'add x y)) (define (sub x y) (apply-generic 'sub x y)) (define (mul x y) (apply-generic 'mul x y)) (define (div x y) (apply-generic 'div x y))`	`function add(x, y) { return apply_generic("add", list(x, y)); } function sub(x, y) { return apply_generic("sub", list(x, y)); } function mul(x, y) { return apply_generic("mul", list(x, y)); } function div(x, y) { return apply_generic("div", list(x, y)); }`

We begin by installing a package for handling ordinary numbers, that is, the primitive numbers of our language. We will tag these with the symbol scheme-number. string "javascript_number". The arithmetic operations in this package are the primitive arithmetic procedures functions (so there is no need to define extra procedures functions to handle the untagged numbers). Since these operations each take two arguments, they are installed in the table keyed by the list (scheme-number scheme-number): list("javascript_number", "javascript_number"):

Original

JavaScript

(define (install-scheme-number-package) (define (tag x) (attach-tag 'scheme-number x)) (put 'add '(scheme-number scheme-number) (lambda (x y) (tag (+ x y)))) (put 'sub '(scheme-number scheme-number) (lambda (x y) (tag (- x y)))) (put 'mul '(scheme-number scheme-number) (lambda (x y) (tag (* x y)))) (put 'div '(scheme-number scheme-number) (lambda (x y) (tag (/ x y)))) (put 'make 'scheme-number (lambda (x) (tag x))) 'done)

function install_javascript_number_package() { function tag(x) { return attach_tag("javascript_number", x); } put("add", list("javascript_number", "javascript_number"), (x, y) => tag(x + y)); put("sub", list("javascript_number", "javascript_number"), (x, y) => tag(x - y)); put("mul", list("javascript_number", "javascript_number"), (x, y) => tag(x * y)); put("div", list("javascript_number", "javascript_number"), (x, y) => tag(x / y)); put("make", "javascript_number", x => tag(x)); return "done"; }

Users of the Scheme-number package JavaScript-number package will create (tagged) ordinary numbers by means of the procedure: function:

Original	JavaScript
`(define (make-scheme-number n) ((get 'make 'scheme-number) n))`	`function make_javascript_number(n) { return get("make", "javascript_number")(n); }`

Now that the framework of the generic arithmetic system is in place, we can readily include new kinds of numbers. Here is a package that performs rational arithmetic. Notice that, as a benefit of additivity, we can use without modification the rational-number code from section 2.1.1 as the internal procedures functions in the package:

Original

JavaScript

(define (install-rational-package) ;; internal procedures (define (numer x) (car x)) (define (denom x) (cdr x)) (define (make-rat n d) (let ((g (gcd n d))) (cons (/ n g) (/ d g)))) (define (add-rat x y) (make-rat (+ (* (numer x) (denom y)) (* (numer y) (denom x))) (* (denom x) (denom y)))) (define (sub-rat x y) (make-rat (- (* (numer x) (denom y)) (* (numer y) (denom x))) (* (denom x) (denom y)))) (define (mul-rat x y) (make-rat (* (numer x) (numer y)) (* (denom x) (denom y)))) (define (div-rat x y) (make-rat (* (numer x) (denom y)) (* (denom x) (numer y)))) ;; interface to rest of the system (define (tag x) (attach-tag 'rational x)) (put 'add '(rational rational) (lambda (x y) (tag (add-rat x y)))) (put 'sub '(rational rational) (lambda (x y) (tag (sub-rat x y)))) (put 'mul '(rational rational) (lambda (x y) (tag (mul-rat x y)))) (put 'div '(rational rational) (lambda (x y) (tag (div-rat x y)))) (put 'make 'rational (lambda (n d) (tag (make-rat n d)))) 'done) (define (make-rational n d) ((get 'make 'rational) n d))

We can install a similar package to handle complex numbers, using the tag complex. "complex". In creating the package, we extract from the table the operations make-from-real-imag make_from_real_imag and make-from-mag-ang make_from_mag_ang that were defined by the rectangular and polar packages. Additivity permits us to use, as the internal operations, the same add-complex, add_complex, sub-complex, sub_complex, mul-complex, mul_complex, and div-complex div_complex procedures functions from section 2.4.1.

Original

JavaScript

(define (install-complex-package) ;; imported procedures from rectangular and polar packages (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)) ;; internal procedures (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)))) ;; interface to rest of the system (define (tag z) (attach-tag 'complex z)) (put 'add '(complex complex) (lambda (z1 z2) (tag (add-complex z1 z2)))) (put 'sub '(complex complex) (lambda (z1 z2) (tag (sub-complex z1 z2)))) (put 'mul '(complex complex) (lambda (z1 z2) (tag (mul-complex z1 z2)))) (put 'div '(complex complex) (lambda (z1 z2) (tag (div-complex z1 z2)))) (put 'make-from-real-imag 'complex (lambda (x y) (tag (make-from-real-imag x y)))) (put 'make-from-mag-ang 'complex (lambda (r a) (tag (make-from-mag-ang r a)))) 'done)

Programs outside the complex-number package can construct complex numbers either from real and imaginary parts or from magnitudes and angles. Notice how the underlying procedures, functions, originally defined in the rectangular and polar packages, are exported to the complex package, and exported from there to the outside world.

Original	JavaScript
`(define (make-complex-from-real-imag x y) ((get 'make-from-real-imag 'complex) x y)) (define (make-complex-from-mag-ang r a) ((get 'make-from-mag-ang 'complex) r a))`	`function make_complex_from_real_imag(x, y){ return get("make_from_real_imag", "complex")(x, y); } function make_complex_from_mag_ang(r, a){ return get("make_from_mag_ang", "complex")(r, a); }`

What we have here is a two-level tag system. A typical complex number, such as $3+4i$ in rectangular form, would be represented as shown in figure 2.37. figure 2.38. The outer tag (complex) ("complex") is used to direct the number to the complex package. Once within the complex package, the next tag (rectangular) ("rectangular") is used to direct the number to the rectangular package. In a large and complicated system there might be many levels, each interfaced with the next by means of generic operations. As a data object is passed downward, the outer tag that is used to direct it to the appropriate package is stripped off (by applying contents) and the next level of tag (if any) becomes visible to be used for further dispatching.

Original		JavaScript
Figure 2.37 Representation of $3+4i$ in rectangular form.		Figure 2.38 Representation of $3+4i$ in rectangular form.

In the above packages, we used add-rat, add_rat, add-complex, add_complex, and the other arithmetic procedures functions exactly as originally written. Once these declarations are internal to different installation procedures, functions, however, they no longer need names that are distinct from each other: we could simply name them add, sub, mul, and div in both packages.

Exercise 2.81 Louis Reasoner tries to evaluate the expression (magnitude z) magnitude(z) where z is the object shown in figure 2.37. figure 2.38. To his surprise, instead of the answer $5$ he gets an error message from apply-generic, apply_generic, saying there is no method for the operation magnitude on the types (complex). list("complex"). He shows this interaction to Alyssa P. Hacker, who says The problem is that the complex-number selectors were never defined for complex "complex" numbers, just for polar "polar" and rectangular "rectangular" numbers. All you have to do to make this work is add the following to the complex package:

Original	JavaScript
`(put 'real-part '(complex) real-part) (put 'imag-part '(complex) imag-part) (put 'magnitude '(complex) magnitude) (put 'angle '(complex) angle)`	`put("real_part", list("complex"), real_part); put("imag_part", list("complex"), imag_part); put("magnitude", list("complex"), magnitude); put("angle", list("complex"), angle);`

Describe in detail why this works. As an example, trace through all the procedures functions called in evaluating the expression (magnitude z) magnitude(z) where z is the object shown in figure 2.37. figure 2.38. In particular, how many times is apply-generic apply_generic invoked? What procedure function is dispatched to in each case?

Putting the above lines to the package will open up z, and those lines act as a pass-through. apply-generic apply_generic will be invoked twice. We shall trace with substitution model how the program evaluates.

Original

JavaScript

;;*** Use substitution rule: (magnitude z) ;;** First apply-generic: (apply-generic 'magnitude z) ;; where z is the whole object including symbol 'complex. ;;recall (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)))))) ;; substitution (let ((type-tags '(complex)) ... )) (let ((proc (get op '(complex))) ... )) (let ((proc magnitude) ... )) (if proc... ;; true (apply magnitude (contents z)) (magnitude z-prime) ;; where z-prime is the contents (the cdr) of the original ;; object, that is, with the 'complex stripped off. ;;** Second apply-generic: (let ((type-tags '(rectangular)) ... )) (let ((proc (get op '(rectangular))) ... )) (let ((proc (get 'magnitude '(rectangular))) ... )) (let ((proc (lambda (z) (sqrt (+ (square (real-part z)) (square (imag-part z)))))) ... ))) (if proc... ;; true (apply (lambda (z) (sqrt (+ (square (real-part z)) (square (imag-part z))))) (contents z-prime)) (sqrt (+ (square 3) (square 4))) 5

magnitude(z); apply_generic("magnitude", list(z)); // In this case: // type_tags = map(type_tag, list(z)) // Which evaluates to: // type_tags = list("complex"); // and // fun = get("magnitude", list("complex")); // which, due to the addition of // put("magnitude", list("complex"), magnitude); // fun = magnitude; apply(magnitude, map(contents, list(z))); apply(magnitude, pair("rectangular", pair(3, 4))); magnitude(pair("rectangular"), pair(3, 4)); apply_generic("magnitude", list(pair("rectangular"), pair(3, 4))); // type_tags = map(type_tag, list(z)) evaluates to list("rectangular") // fun = get("magnitude", list("rectangular")) which evaluates to // z => math_sqrt(square(real_part(z)) + square(imag_part(z))) // z => math_sqrt(square(head(z)) + square(tail(z))) apply(fun, map(contents, list(pair("rectangular"), pair(3, 4)))) apply(fun, pair(3, 4)) (z => math_sqrt(square(head(z)) + square(tail(z))))(pair(3, 4)); math_sqrt(square(head(pair(3, 4))) + square(tail(pair(3, 4)))) ... math_sqrt(square(3) + square(4)); ... math_sqrt(9 + 16); math_sqrt(25); 5

Exercise 2.82 The internal procedures functions in the scheme-number javascript_number package are essentially nothing more than calls to the primitive procedures functions +, -, etc. It was not possible to use the primitives of the language directly because our type-tag system requires that each data object have a type attached to it. In fact, however, all Lisp JavaScript implementations do have a type system, which they use internally. Primitive predicates such as symbol? is_string and number? is_number determine whether data objects have particular types. Modify the definitions of type-tag, type_tag, contents, and attach-tag attach_tag from section 2.4.2 so that our generic system takes advantage of Scheme's JavaScript's internal type system. That is to say, the system should work as before except that ordinary numbers should be represented simply as Scheme JavaScript numbers rather than as pairs whose car head is the symbol scheme-number. string "javascript_number".

The following modifications will take advantage of the JavaScript number implementation:

Original

JavaScript

(define (attach-tag type-tag contents) (if (number? contents) contents (cons type-tag contents))) (define (type-tag datum) (cond ((number? datum) 'scheme-number) ((pair? datum) (car datum)) (else (error "Wrong datum -- TYPE-TAG" datum)))) (define (contents datum) (cond ((number? datum) datum) ((pair? datum) (cdr datum)) (else (error "Wrong datum -- CONTENTS" datum))))

function attach_tag(type_tag, contents) { return is_number(contents) ? pair("javascript_number", contents) : pair(type_tag, contents); } function type_tag(datum) { return is_number(datum) ? "javascript_number" : is_pair(datum) ? head(datum) : error(datum, "bad tagged datum -- type_tag"); } function contents(datum) { return is_number(datum) ? datum : is_pair(datum) ? tail(datum) : error(datum, "bad tagged datum -- contents"); }

Exercise 2.83 Define a generic equality predicate equ? is_equal that tests the equality of two numbers, and install it in the generic arithmetic package. This operation should work for ordinary numbers, rational numbers, and complex numbers.

// provided by GitHub user clean99 function is_equal(x, y) { return apply_generic("is_equal", list(x, y)); } function install_javascript_number_package() { // ... put("is_equal", list("javascript_number", "javascript_number"), (x, y) => x === y); // ... } function install_rational_package() { // ... function is_equal(x, y) { return numer(x) * denom(y) === numer(y) * denom(x); } put("is_equal", list("rational", "rational"), is_equal); // ... } function install_complex_package() { // ... function is_equal(z1, z2) { return real_part(z1) === real_part(z2) ? imag_part(z1) === imag_part(z2) : false; } put("is_equal", list("complex", "complex"), is_equal); //... }

Exercise 2.84 Define a generic predicate =zero? is_equal_to_zero that tests if its argument is zero, and install it in the generic arithmetic package. This operation should work for ordinary numbers, rational numbers, and complex numbers.

// provided by GitHub user clean99 function is_equal_to_zero(x) { return apply_generic("is_equal_to_zero", list(x)); } function install_javascript_number_package() { // ... put("is_equal_to_zero", "javascript_number", x => x === 0); // ... } function install_rational_package() { // ... function is_equal_to_zero(x) { return numer(x) === 0; } put("is_equal_to_zero", "rational", is_equal_to_zero); // ... } function install_complex_package() { // ... function is_equal_to_zero(z) { return real_part(z) === 0 ? imag_part(z) === 0 : false; } put("is_equal_to_zero", "complex", is_equal_to_zero); //... }