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 procedures functions numer, denom, and make-rat make_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:

Original

Python

(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)))) (define (equal-rat? x y) (= (* (numer x) (denom y)) (* (numer y) (denom x))))

def add_rat(x, y): return make_rat(numer(x) * denom(y) + numer(y) * denom(x), denom(x) * denom(y)) def sub_rat(x, y): return make_rat(numer(x) * denom(y) - numer(y) * denom(x), denom(x) * denom(y)) def mul_rat(x, y): return make_rat(numer(x) * numer(y), denom(x) * denom(y)) def div_rat(x, y): return make_rat(numer(x) * denom(y), denom(x) * numer(y)) def 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 procedures functions numer, 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 Python environment provides a compound structure called a pair, which can be constructed with the primitive procedure primitive function cons. pair. This procedure 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 procedures functions car head and cdrtail.[1] Thus, we can use cons, pair, car, head, and cdr tail as follows:

Original	Python
(define x (cons 1 2))	x = pair(1, 2)

Original	Python
(car x) 1	print(head(x)) 1

Original	Python
(cdr x) 2	print(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, cons pair can be used to form pairs whose elements are pairs, and so on:

Original	Python
(define x (cons 1 2)) (define y (cons 3 4)) (define z (cons x y))	x = pair(1, 2) y = pair(3, 4) z = pair(x, y)

Original	Python
(car (car z)) 1	print(head(head(z))) 1

Original	Python
(car (cdr z)) 3	print(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 procedures functions cons, 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	Python
(define (make-rat n d) (cons n d)) (define (numer x) (car x)) (define (denom x) (cdr x))	def make_rat(n, d): return pair(n, d) def numer(x): return head(x) def 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

Original		Python
denominator:[3]		denominator. We use the primitive function str to turn any value (here a number) into a string. The operator + in Python 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.

Original	Python
(define (print-rat x) (newline) (display (numer x)) (display "/") (display (denom x)))	def print_rat(x): print(str(numer(x)) + " / " + str(denom(x)))

Now we can try our rational-number procedures: functions:

Original	Python
(define one-half (make-rat 1 2)) (print-rat one-half) 1/2	one_half = make_rat(1, 2) print(print_rat(one_half)) 1 / 2

Original	Python
(define one-third (make-rat 1 3))	one_third = make_rat(1, 3)

Original	Python
(print-rat (add-rat one-half one-third)) 5/6	print(print_rat(add_rat(one_half, one_third))) 5 / 6

Original	Python
(print-rat (mul-rat one-half one-third)) 1/6	print(print_rat(mul_rat(one_half, one_third))) 1 / 6

Original	Python
(print-rat (add-rat one-third one-third)) 6/9	print(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. make_rat. If we have a gcd procedure 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:

Original	Python
(define (make-rat n d) (let ((g (gcd n d))) (cons (/ n g) (/ d g))))	def make_rat(n, d): g = gcd(n, d) return pair(n // g, d // g)

Now we have

Original	Python
(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-rat make_rat without changing any of the procedures functions (such as add-rat add_rat and mul-rat) mul_rat) that implement the actual operations.

Exercise 2.1 Define a better version of make-rat make_rat that handles both positive and negative arguments. Make-rat 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.

Solution

Original	Python
	def sign(x): return -1 if x < 0 else (1 if x > 0 else 0) def make_rat(n, d): g = gcd(n, d) return pair(sign(n) * sign(d) * abs(n // g), abs(d // g))