Chapter 2

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

Consider the problem of representing line segments in a plane. Each segment is represented as a pair of points: a starting point and an ending point. Define a constructor make-segment and selectors start-segment and end-segment that define the representation of segments in terms of points. Furthermore, a point can be represented as a pair of numbers: the \(x\) coordinate and the \(y\) coordinate. Accordingly, specify a constructor make-point and selectors \(\mathrm{x}\)-point and y-point that define this representation. Finally, using your selectors and constructors, define a procedure midpoint-segment that takes a line segment as argument and returns its midpoint (the point whose coordinates are the average of the coordinates of the endpoints). To try your procedures, you'll need a way to print points: (define (print-point p) (newline) (display " (") (display (x-point p)) (display ",") (display ( \(\mathrm{y}\)-point \(\mathrm{p}\) )) (display ")"))

Here is an alternative procedural representation of pairs. For this representation, verify that (car (cons \(\mathrm{x} \mathrm{y}\) )) yields \(\mathrm{x}\) for any objects \(\mathrm{x}\) and \(\mathrm{y}\). (define (cons \(\mathrm{x} \mathrm{y}\) ) \(\quad(\) lambda \((\mathrm{m})(\mathrm{m} \mathrm{x} \mathrm{y})))\) \((\) define \((\mathrm{car} \mathrm{z})\) \((\mathrm{z}(\) lambda \((\mathrm{p} \mathrm{q}) \mathrm{p})))\) What is the corresponding definition of cdr? (Hint: To verify that this works, make use of the substitution model of section 1.1.5.)

Show that we can represent pairs of nonnegative integers using only numbers and arithmetic operations if we represent the pair \(a\) and \(b\) as the integer that is the product \(2^{a} 3^{b}\). Give the corresponding definitions of the procedures cons, car, and cdr.

In case representing pairs as procedures wasn't mind-boggling enough, consider that, in a language that can manipulate procedures, we can get by without numbers (at least insofar as nonnegative integers are concerned) by implementing 0 and the operation of adding 1 as (define zero (lambda (f) (lambda ( \(x\) ) \(x\) ))) (define (add-1 \({n}\) ) (lambda (f) (lambda ( \(x\) ) (f ( \((\) n \(f) x))\) )) This representation is known as Church numerals, after its inventor, Alonzo Church, the logician who invented the \(\lambda\) calculus. Define one and two directly (not in terms of zero and add-1). (Hint: Use substitution to evaluate (add-1 zero)). Give a direct definition of the addition procedure + (not in terms of repeated application of add-1).

Alyssa's program is incomplete because she has not specified the implementation of the interval abstraction. Here is a definition of the interval constructor: (define (make-interval a b) (cons a b)) Define selectors upper-bound and lower-bound to complete the implementation.

Show that under the assumption of small percentage tolerances there is a simple formula for the approximate percentage tolerance of the product of two intervals in terms of the tolerances of the factors. You may simplify the problem by assuming that all numbers are positive.

Explain, in general, why equivalent algebraic expressions may lead to different answers. Can you devise an interval-arithmetic package that does not have this shortcoming, or is this task impossible? (Waming: This problem is very difficult.)

Define a procedure last-pair that returns the list that contains only the last element of a given (nonempty) list: (last-pair (list 2372149 34)) (34)

Define a procedure reverse that takes a list as argument and returns a list of the same elements in reverse order: (reverse (list 1491625 ) ) \(\left(\begin{array}{llllllll}25 & 16 & 9 & 4 & 1\end{array}\right)\)