SICP Exercise 2.3: Rectangles

Implement a representation for rectangles in a plane. (Hint: You may want to make use of exercise 2.2.) In terms of your constructors and selectors, create procedures that compute the perimeter and the area of a given rectangle. Now implement a different representation for rectangles. Can you design your system with suitable abstraction barriers, so that the same perimeter and area procedures will work using either representation?

To make this easy on ourselves, let's assume that the sides of our rectangles run parallel to the axes. Then we can easily produce a couple of representations for rectangles:

1. Have two points to represent diagonally opposite corners of the rectangle.
2. Have a point to represent a single corner and the width and height for the rectangle.

We defined a constructor and selectors for points in exercise 2.2, so we can use those here.

Let's start with the first representation. We want our constructor to take two points, and we can put these in a pair:

(define (make-rect p1 p2)
  (cons p1 p2))

What selectors shall we have? Well, let's try to cover all bases. We'll have selectors for the four corner points, one to get the width and one to get the height. Note that to select any particular corner point we can take the two points the rectangle was constructed with, extract their x and y components and create a new point using either the smaller or larger of the two x values and either the smaller or larger of the two y values. Whether we select the smaller or larger for each value depends upon which corner it is:

Corner	x Value	y Value
Bottom Left	Smaller	Smaller
Bottom Right	Larger	Smaller
Top Left	Smaller	Larger
Top Right	Larger	Larger

Scheme provides a couple of procedures as standard, min and max, which we can use to select the appropriate values in each case. For example, we could define our procedure to get the bottom-right point as:

(define (get-bottom-right r)
  (let ((p1 (car r))
        (p2 (cdr r)))
    (make-point (min (x-point p1) (x-point p2))
                (max (y-point p1) (y-point p2)))))

However, we can take this a step further. All of the corner selectors will follow this same pattern, so we can extract out a higher-order procedure that takes in the rectangle and the two procedures that select which x and y values to use. Then each of our corner selectors can just invoke this appropriately:

(define (get-point r xselector yselector)
  (let ((p1 (car r))
        (p2 (cdr r)))
    (make-point (xselector (x-point p1) (x-point p2))
                (yselector (y-point p1) (y-point p2)))))

(define (get-bottom-left r)
  (get-point r min min))

(define (get-bottom-right r)
  (get-point r max min))

(define (get-top-left r)
  (get-point r min max))

(define (get-top-right r)
  (get-point r max max))

Finally we need the width and height selectors. These can just find the absolute difference between the x or y values of the two points respectively:

(define (get-width r)
  (abs (- (x-point (car r)) (x-point (cdr r)))))

(define (get-height r)
  (abs (- (y-point (car r)) (y-point (cdr r)))))

We could, of course, have extracted another higher-order procedure here that takes the rectangle and the value selector (i.e. x-point or y-point) and performs the calculation. However in this case, given that the calculation is a simple single-line expression and there are only two occurrences of it, I'm happy to leave them as is.

Let's see this in action:

> (define r1 (make-rect (make-point 1 3) (make-point 6 5)))
> (define r2 (make-rect (make-point 7 5) (make-point 3 4)))
> (get-bottom-left r1)
(1 . 3)
> (get-bottom-right r1)
(6 . 3)
> (get-top-left r1)
(1 . 5)
> (get-top-right r1)
(6 . 5)
> (get-width r1)
5
> (get-height r1)
2
> (get-bottom-left r2)
(3 . 4)
> (get-bottom-right r2)
(7 . 4)
> (get-top-left r2)
(3 . 5)
> (get-top-right r2)
(7 . 5)
> (get-width r2)
4
> (get-height r2)
1

Now that we've defined our constructor and selectors we can move on to defining the procedures for calculating the perimeter and area of a rectangle. Given a rectangle of width w and height h we know we can calculate the perimeter as 2(w+h) and the area as wh. Handily, we have selectors for the width and height of a rectangle, so we can translate these formulae pretty directly into procedures:

(define (perimeter r)
  (* 2 (+ (get-width r) (get-height r))))

(define (area r)
  (* (get-width r) (get-height r)))

And let's put these to the test:

> (perimeter r1)
14
> (perimeter r2)
10
> (area r1)
10
> (area r2)
4

Okay, so that all seems to work, so let's move on to the second representation. Now if we allow the width and/or height to be negative then the corner point can be any of the points of the rectangle. For example, if we have a positive width and negative height then the point will represent the top-left corner. Let's see if we can put this into practice:

(define (make-rect p w h)
  (cons p (cons w h)))

(define (get-point r xselector yselector)
  (let ((p (car r)))
    (make-point (xselector (x-point p) (+ (x-point p) (cadr r)))
                (yselector (y-point p) (+ (y-point p) (cddr r))))))

(define (get-bottom-left r)
  (get-point r min min))

(define (get-bottom-right r)
  (get-point r max min))

(define (get-top-left r)
  (get-point r min max))

(define (get-top-right r)
  (get-point r max max))

(define (get-width r)
  (abs (cadr r)))

(define (get-height r)
  (abs (cddr r)))

And here's the second representation in action...

> (define r1 (make-rect (make-point 1 3) 5 2))
> (define r2 (make-rect (make-point 7 5) -4 -1))
> (get-bottom-left r1)
(1 . 3)
> (get-bottom-right r1)
(6 . 3)
> (get-top-left r1)
(1 . 5)
> (get-top-right r1)
(6 . 5)
> (get-width r1)
5
> (get-height r1)
2
> (get-bottom-left r2)
(3 . 4)
> (get-bottom-right r2)
(7 . 4)
> (get-top-left r2)
(3 . 5)
> (get-top-right r2)
(7 . 5)
> (get-width r2)
4
> (get-height r2)
1
> (perimeter r1)
14
> (perimeter r2)
10
> (area r1)
10
> (area r2)
4

SICP Exercise 2.2: Points and Segments

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 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 (y-point p))
  (display ")"))

Well, we've just been introduced to pairs, so it seems reasonable to use those to represent segments and points. A segment can be a pair of points, and a point can be a pair of coordinates. In each case we're going to have two selectors that will use car and cdr to retrieve the components of the data structure. Here's my definitions:

(define (make-segment p1 p2) (cons p1 p2))
(define (start-segment s) (car s))
(define (end-segment s) (cdr s))

(define (make-point x y) (cons x y))
(define (x-point p) (car p))
(define (y-point p) (cdr p))

Next we're asked to define midpoint-segment. The midpoint of a segment is a point with its x coordinate equal to the average of the x coordinates of the start and end points, and its y coordinate equal to the average of the y coordinates of the start and end points. So our midpoint-segment is going to have to use the segment point selectors to access the start and end points of the segment, and the point x and y selectors to access the components of those points. I'm going to make use of the average procedure that was defined way back in section 1.1.7 to help produce this procedure:

(define (midpoint-segment s)
  (make-point (average (x-point (start-segment s)) (x-point (end-segment s)))
              (average (y-point (start-segment s)) (y-point (end-segment s)))))

Finally, let's see it all in action:

> (print-point (midpoint-segment (make-segment (make-point 0 0) (make-point 4 4))))
(2,2)
> (print-point (midpoint-segment (make-segment (make-point 1 2) (make-point 5 4))))
(3,3)
> (print-point (midpoint-segment (make-segment (make-point 4 -2) (make-point -3 8))))
(1/2,3)

SICP Exercise 2.1: More Rational Rational Numbers

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.

Here's the original make-rat:

(define (make-rat n d)
  (let ((g (gcd n d)))
    (cons (/ n g) (/ d g))))

Before we start into changing this, first let's define what we mean by a positive versus a negative rational number. It's all in the signs... A rational number is positive if the numerator and denominator have the same sign and negative if the numerator and denominator have different signs.

So if the arguments to make-rat are either both positive or both negative then we want make-rat to convert both the numerator and denominator to their absolute values. If, on the other hand, the arguments have different signs then we want make-rat to ensure that the numerator has a negative sign and converts the denominator to its absolute value.

Looking at the denominator first, we always want that to be converted to its absolute value. This can be easily achieved by applying abs to the passed denominator argument, d.

As for the numerator, we know we can change the sign of a number by multiplying it by -1 and that multiplying a number by 1 leaves the sign unchanged. Let's look at what we'd have to multiply the numerator by in the various cases to get the effect we want:

Numerator Sign	Denominator Sign	Desired Numerator Sign	Multiplicand
+ve	+ve	+ve	1
-ve	-ve	+ve	-1
-ve	+ve	-ve	1
+ve	-ve	-ve	-1

As you can see, the multiplicand we want to use corresponds to the sign of the denominator. Handily there's a standard mathematical function, the sign, or signum, function, that will return 1, 0 or -1 depending upon whether the argument is positive, zero or negative. So we can apply this to the denominator and multiply the numerator by the result.

Unfortunately signum is not a standard scheme function. DrRacket, the interpreter I'm using, has a predefined procedure, sng, that provides this functionality. If you're using something else then you can define it as:

(define (sgn x)
  (if (= x 0)
      0
      (/ (abs x) x)))

Assuming we've got sgn to hand we can then define our updated make-rat as:

(define (make-rat n d)
  (let ((g (gcd n d)))
    (cons (/ (* n (sgn d)) g) (/ (abs d) g))))

And then, assuming we've also got print-rat and the supporting procedures from section 2.1.1, we can put it into practice:

> (print-rat (make-rat 4 5))
4/5
> (print-rat (make-rat 4 -5))
-4/5
> (print-rat (make-rat -4 5))
-4/5
> (print-rat (make-rat -4 -5))
4/5