2.1.1 Example: Arithmetic Operations for Rational Numbers

Permalink copied!

2.1.1

Example: Arithmetic Operations for Rational Numbers

Suppose we want to do arithmetic with rational numbers. We want to be able to add, subtract, multiply, and divide them and to test whether two rational numbers are equal.

Let us begin by assuming that we already have a way of constructing a rational number from a numerator and a denominator. We also assume that, given a rational number, we have a way of extracting (or selecting) its numerator and its denominator. Let us further assume that the constructor and selectors are available as functions:

make_rat($n$, $d$) returns the rational number whose numerator is the integer $n$ and whose denominator is the integer $d$.
numer($x$) returns the numerator of the rational number $x$.
denom($x$) returns the denominator of the rational number $x$.

We are using here a powerful strategy of synthesis: wishful thinking. We haven't yet said how a rational number is represented, or how the functions numer, denom, and make_rat should be implemented. Even so, if we did have these three functions, we could then add, subtract, multiply, divide, and test equality by using the following relations:

\[ \begin{array}{rll} \dfrac{n_{1}}{d_{1}}+\dfrac{n_{2}}{d_{2}} &=&\dfrac{n_{1}d_{2}+n_{2}d_{1}}{d_{1}d_{2}}\\[15pt] \dfrac{n_{1}}{d_{1}}-\dfrac{n_{2}}{d_{2}} &=&\dfrac{n_{1}d_{2}-n_{2}d_{1}}{d_{1}d_{2}}\\[15pt] \dfrac{n_{1}}{d_{1}}\cdot\dfrac{n_{2}}{d_{2}} &=&\dfrac{n_{1}n_{2}}{d_{1}d_{2}}\\[15pt] \dfrac{n_{1}/d_{1}}{n_{2}/d_{2}} &=&\dfrac{n_{1}d_{2}}{d_{1}n_{2}}\\[15pt] \dfrac{n_{1}}{d_{1}} &=&\dfrac{n_{2}}{d_{2}}\ \quad \textrm{if and only if}\ \ \ n_{1}d_{2}\ =\ n_{2}d_{1} \end{array} \]

We can express these rules as functions:

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));
}
function equal_rat(x, y) {
    return numer(x) * denom(y) === numer(y) * denom(x);
}

Now we have the operations on rational numbers defined in terms of the selector and constructor functions numer, denom, and make_rat. But we haven't yet defined these. What we need is some way to glue together a numerator and a denominator to form a rational number.

Pairs
ペア

To enable us to implement the concrete level of our data abstraction, our JavaScript environment provides a compound structure called a pair, which can be constructed with the primitive function pair. This function takes two arguments and returns a compound data object that contains the two arguments as parts. Given a pair, we can extract the parts using the primitive functions head and tail. Thus, we can use pair, head, and tail as follows:

const x = pair(1, 2);

head(x);

tail(x);

Notice that a pair is a data object that can be given a name and manipulated, just like a primitive data object. Moreover, pair can be used to form pairs whose elements are pairs, and so on:

const x = pair(1, 2);

const y = pair(3, 4);

const z = pair(x, y);

head(head(z));

head(tail(z));

In section 2.2 we will see how this ability to combine pairs means that pairs can be used as general-purpose building blocks to create all sorts of complex data structures. The single compound-data primitive pair, implemented by the functions pair, head, and tail, is the only glue we need. Data objects constructed from pairs are called list-structured data.

Representing rational numbers
有理数の表現

Pairs offer a natural way to complete the rational-number system. Simply represent a rational number as a pair of two integers: a numerator and a denominator. Then make_rat, numer, and denom are readily implemented as follows:

[1]

function make_rat(n, d) { return pair(n, d); }

function numer(x) { return head(x); }

function denom(x) { return tail(x); }

Also, in order to display the results of our computations, we can print rational numbers by printing the numerator, a slash, and the

denominator. We use the primitive function stringify to turn any value (here a number) into a string. The operator + in JavaScript is overloaded; it can be applied to two numbers or to two strings, and in the latter case it returns the result of concatenating the two strings.

[2]

function print_rat(x) {
    return display(stringify(numer(x)) + " / " + stringify(denom(x)));
}

Now we can try our rational-number functions:

[3]

const one_half = make_rat(1, 2);

print_rat(one_half);

"1 / 2"

const one_third = make_rat(1, 3);

print_rat(add_rat(one_half, one_third));

"5 / 6"

print_rat(mul_rat(one_half, one_third));

"1 / 6"

print_rat(add_rat(one_third, one_third));

"6 / 9"

As the final example shows, our rational-number implementation does not reduce rational numbers to lowest terms. We can remedy this by changing make_rat. If we have a gcd function like the one in section 1.2.5 that produces the greatest common divisor of two integers, we can use gcd to reduce the numerator and the denominator to lowest terms before constructing the pair:

function make_rat(n, d) {
    const g = gcd(n, d);
    return pair(n / g, d / g);
}

Now we have

print_rat(add_rat(one_third, one_third));

"2 / 3"

as desired. This modification was accomplished by changing the constructor make_rat without changing any of the functions (such as add_rat and mul_rat) that implement the actual operations.

Exercise 2.1

Define a better version of make_rat that handles both positive and negative arguments. The function make_rat should normalize the sign so that if the rational number is positive, both the numerator and denominator are positive, and if the rational number is negative, only the numerator is negative.

function sign(x) {
    return x < 0 
           ? -1
	   : x > 0
	     ? 1
	     : 0;
}
function make_rat(n, d) {
    const g = gcd(n, d);
    return pair(sign(n) * sign(d) * abs(n / g), 
                abs(d / g));
}

[1]

Another way to define the selectors and constructor is

const make_rat = pair;
const numer = head;
const denom = tail;

The first definition associates the name make_rat with the value of the expression pair, which is the primitive function that constructs pairs. Thus make_rat and pair are names for the same primitive constructor.

Defining selectors and constructors in this way is efficient: Instead of make_rat calling pair, make_rat is pair, so there is only one function called, not two, when make_rat is called. On the other hand, doing this defeats debugging aids that trace function calls or put breakpoints on function calls: You may want to watch make_rat being called, but you certainly don't want to watch every call to pair.

We have chosen not to use this style of definition in this book.

[2]

In JavaScript, the operator + can also be applied to a string and a number and to other operand combinations, but in this book, we choose to apply it either to two numbers or to two strings.

[3]

The primitive function display introduced in exercise 1.22 returns its argument, but in the uses of print_rat below, we show only what print_rat prints, not what the interpreter prints as the value returned by print_rat.

< Previous

Next >

2.1.1

Example: Arithmetic Operations for Rational Numbers

Pairsペア

Representing rational numbers有理数の表現

Pairs
ペア

Representing rational numbers
有理数の表現