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
procedures:functions:
(make-rat n d)make_rat($n$, $d$)
returns the
rational number whose numerator is the integer
$n$ and whose denominator is the integer
$d$.
(numer x)numer($x$)
returns the numerator of the rational number
$x$.
(denom 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
proceduresfunctionsnumer, denom, and
make-ratmake_rat
should be implemented. Even so, if we did have these three
procedures,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
procedures:functions:
Now we have the operations on rational numbers defined in terms of the
selector and constructor
proceduresfunctionsnumer, denom, and
make-rat.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
language
JavaScript environment
provides a compound structure called a
pair, which can be constructed with the
primitive procedureprimitive functioncons.pair.
This
procedurefunction
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
proceduresfunctionscarhead
and
cdrtail.[1]
Thus, we can use
cons,pair,car,head,
and
cdrtail
as follows:
Original
JavaScript
(define x (cons 1 2))
const x = pair(1, 2);
Original
JavaScript
(car x)
1
head(x);
1
Original
JavaScript
(cdr x)
2
tail(x);
2
Notice that a pair is a data object that can be given a name and
manipulated, just like a primitive data object. Moreover,
conspair
can be used to form pairs whose elements are pairs, and so on:
Original
JavaScript
(define x (cons 1 2))
(define y (cons 3 4))
(define z (cons x y))
const x = pair(1, 2);
const y = pair(3, 4);
const z = pair(x, y);
Original
JavaScript
(car (car z))
1
head(head(z));
1
Original
JavaScript
(car (cdr z))
3
head(tail(z));
3
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
proceduresfunctionscons,pair,car,head,
and
cdr,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,make_rat,numer, and denom
are readily implemented as follows:[2]
Original
JavaScript
(define (make-rat n d) (cons n d))
(define (numer x) (car x))
(define (denom x) (cdr x))
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.[4]
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.make_rat.
If we have a
gcdprocedurefunction
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:
Original
JavaScript
(define (make-rat n d)
(let ((g (gcd n d)))
(cons (/ n g) (/ d g))))
function make_rat(n, d) {
const g = gcd(n, d);
return pair(n / g, d / g);
}
Now we have
Original
JavaScript
(print-rat (add-rat one-third one-third))
2/3
print_rat(add_rat(one_third, one_third));
"2 / 3"
as desired. This modification was accomplished by changing the constructor
make-ratmake_rat
without changing any of the
proceduresfunctions
(such as
add-ratadd_rat
and
mul-rat)mul_rat)
that implement the actual operations.
Exercise 2.1
Define a better version of
make-ratmake_rat
that handles both positive and negative arguments.
Make-ratThe 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.
Original
JavaScript
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]
The name
cons stands for construct.
The names
car and
cdr derive from the original implementation
of Lisp on the
IBM 704. That machine had an addressing scheme that allowed one to
reference the address and decrement parts of
a memory location. Car stands for
Contents of Address part of Register and
cdr (pronounced could-er)
stands for Contents of Decrement part of
Register.
[2]
Another way to define the selectors and constructor is
Original
JavaScript
(define make-rat cons)
(define numer car)
(define denom cdr)
The first definition associates the name
make-ratmake_rat
with the value of the expression
cons,pair,
which is the primitive
procedurefunction
that constructs pairs. Thus
make-ratmake_rat
and
conspair
are names for the same primitive constructor.
Defining selectors and constructors in this way is efficient: Instead of
make-ratmake_ratcallingcons,pair,make-ratmake_ratiscons,pair,
so there is only one
procedurefunction
called, not two, when
make-ratmake_rat
is called. On the other hand, doing this defeats debugging aids that
trace
procedurefunction
calls or put breakpoints on
procedurefunction
calls:
You may want to watch
make-ratmake_rat
being called, but you certainly don't want to watch every call to
cons.pair.
We have chosen not to use this style of definition in this book.
[3] Display is
the Scheme primitive for
printing data. The Scheme primitive
newline starts a new line for printing.
Neither of these procedures returns a useful value, so 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.
[4]
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.
[5]
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.