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 function add that acts like ordinary primitive addition + on ordinary numbers, like add_rat on rational numbers, and like 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 function to dispatch to an appropriate package according to the data type of its arguments.

The generic arithmetic functions are defined as follows:

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 tag these with the string "javascript_number". The arithmetic operations in this package are the primitive arithmetic functions (so there is no need to define extra functions to handle the untagged numbers). Since these operations each take two arguments, they are installed in the table keyed by the list list("javascript_number", "javascript_number"):

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 JavaScript-number package will create (tagged) ordinary numbers by means of the function:

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 functions in the package:

function install_rational_package() {
    // internal functions
    function numer(x) { return head(x); }
    function denom(x) { return tail(x); }
    function make_rat(n, d) {
        const g = gcd(n, d);
        return pair(n / g, d / g);
    }
    function add_rat(x, y) {
        return make_rat(numer(x) * denom(y) + numer(y) * denom(x),
                        denom(x) * denom(y));
    }
    function sub_rat(x, y) {
        return make_rat(numer(x) * denom(y) - numer(y) * denom(x),
                        denom(x) * denom(y));
    }
    function mul_rat(x, y) {
        return make_rat(numer(x) * numer(y),
                        denom(x) * denom(y));
    }
    function div_rat(x, y) {
        return make_rat(numer(x) * denom(y),
                        denom(x) * numer(y));
    }
    // interface to rest of the system
    function tag(x) {
        return attach_tag("rational", x);
    }
    put("add", list("rational", "rational"),
        (x, y) => tag(add_rat(x, y)));
    put("sub", list("rational", "rational"),
        (x, y) => tag(sub_rat(x, y)));
    put("mul", list("rational", "rational"),
        (x, y) => tag(mul_rat(x, y)));
    put("div", list("rational", "rational"),
        (x, y) => tag(div_rat(x, y)));
    put("make", "rational",
        (n, d) => tag(make_rat(n, d)));
    return "done";  
}

function make_rational(n, d) {
    return get("make", "rational")(n, d);
}

We can install a similar package to handle complex numbers, using the tag "complex". In creating the package, we extract from the table the operations make_from_real_imag and 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, sub_complex, mul_complex, and div_complex functions from section 2.4.1.

function install_complex_package() {
    // imported functions from rectangular and polar packages
    function make_from_real_imag(x, y) {
        return get("make_from_real_imag", "rectangular")(x, y);
    }
    function make_from_mag_ang(r, a) {
        return get("make_from_mag_ang", "polar")(r, a);
    }
    // internal functions
    function add_complex(z1, z2) {
        return make_from_real_imag(real_part(z1) + real_part(z2),
                                   imag_part(z1) + imag_part(z2));
    }
    function sub_complex(z1, z2) {
        return make_from_real_imag(real_part(z1) - real_part(z2),
                                   imag_part(z1) - imag_part(z2));
    }
    function mul_complex(z1, z2) {
        return make_from_mag_ang(magnitude(z1) * magnitude(z2),
                                 angle(z1) + angle(z2));
    }
    function div_complex(z1, z2) {
        return make_from_mag_ang(magnitude(z1) / magnitude(z2),
                                 angle(z1) - angle(z2));
    }
    // interface to rest of the system
    function tag(z) { return attach_tag("complex", z); }
    put("add", list("complex", "complex"), 
        (z1, z2) => tag(add_complex(z1, z2)));
    put("sub", list("complex", "complex"), 
        (z1, z2) => tag(sub_complex(z1, z2)));
    put("mul", list("complex", "complex"), 
        (z1, z2) => tag(mul_complex(z1, z2)));
    put("div", list("complex", "complex"), 
        (z1, z2) => tag(div_complex(z1, z2)));
    put("make_from_real_imag", "complex", 
        (x, y) => tag(make_from_real_imag(x, y)));
    put("make_from_mag_ang", "complex", 
        (r, a) => tag(make_from_mag_ang(r, a)));
    return "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 functions, originally defined in the rectangular and polar packages, are exported to the complex package, and exported from there to the outside world.

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.38. The outer tag ("complex") is used to direct the number to the complex package. Once within the complex package, the next tag ("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.

Figure 2.38

Representation of $3+4i$ in rectangular form.

In the above packages, we used add_rat, add_complex, and the other arithmetic functions exactly as originally written. Once these declarations are internal to different installation 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.77

Louis Reasoner tries to evaluate the expression magnitude(z) where z is the object shown in figure 2.38. To his surprise, instead of the answer $5$ he gets an error message from apply_generic, saying there is no method for the operation magnitude on the types 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" numbers, just for "polar" and "rectangular" numbers. All you have to do to make this work is add the following to the complex package:

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 functions called in evaluating the expression magnitude(z) where z is the object shown in figure 2.38. In particular, how many times is apply_generic invoked? What 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 will be invoked twice. We shall trace with substitution model how the program evaluates.

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

The internal functions in the javascript_number package are essentially nothing more than calls to the primitive 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 JavaScript implementations do have a type system, which they use internally. Primitive predicates such as is_string and is_number determine whether data objects have particular types. Modify the definitions of type_tag, contents, and attach_tag from section 2.4.2 so that our generic system takes advantage of JavaScript's internal type system. That is to say, the system should work as before except that ordinary numbers should be represented simply as JavaScript numbers rather than as pairs whose head is the string "javascript_number".

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

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

Define a generic equality predicate 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.80

Define a generic predicate 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);

    //...
}