Thursday, October 7, 2010

SICP 2.3: Rectangles in a plane

From SICP section 2.1.2 Abstraction Barriers

Exercise 2.3 asks us to build on the results of exercise 2.2 and implement a representation for rectangles in a plane. In addition to a constructor and selectors for a representation of a rectangle, we'll also need to implement procedures for computing the perimeter and area of a given rectangle. Once we've done that we'll need to implement a different representation for rectangles. The challenge is to design a system with suitable abstraction barriers so that the area and perimeter procedures will work with either rectangle representation.

First let's look at a few different ways to represent rectangles. To simplify things, we'll assume that the sides of the rectangle are to be perpendicular to the x- and y-axes of the coordinate plane.

The most obvious representation would be to combine four points (ignoring the fact that four points might not form a rectangle and just accepting any four points for this representation). We could easily implement this representation since we already have a representation for points in a plane.

Next, we could represent a rectangle as a single point along with a width and a height. This would make it very easy to calculate the perimeter and area of a given rectangle.

Another representation could be to store two opposite corners of the rectangle. This would give us just enough information to calculate the width and the height, from which we can calculate the perimeter and area.

You can probably think of several other representations such as storing all four segments that make up the sides of a rectangle, storing only two adjacent sides, or storing the segment that joins two opposite corners forming a diagonal. These would all work, but some require us to store more information than we really need.

The first implementation will be the third one pictured above where a rectangle is represented by two opposite corners. The constructor will simply join two points together. The selctors will return the width and height of the rectangle. The width and height are calculated by taking the absolute value of the difference between the x- and y-coordinates respectively.
; rectangle constructor; join two opposite corners(define (make-rect a b) (cons a b)); rectangle selectors(define (rect-width r)   (abs (- (x-point (car r)) (x-point (cdr r)))))(define (rect-height r)   (abs (- (y-point (car r)) (y-point (cdr r)))))

With that done, we can implement procedures for computing the perimeter and area of a rectangle.
(define (rect-perimeter r)   (* 2 (+ (rect-width r) (rect-height r))))(define (rect-area r)   (* (rect-width r) (rect-height r)))

We can test it out by defining two points, creating a rectangle, and displaying its perimeter and area.
> (define a (make-point 0 0))> (define b (make-point 2 10))> (define r (make-rect a b))> (display (rect-perimeter r))24> (display (rect-area r))20

The box-and-pointer diagram of the rectangle created above shows how the individual elements are stored. The rectangle itself is made up of two points (from the last exercise), each of which are themselves made up of an x and a y value. The rect-width and rect-height selectors are used to access these x and y values to calculate the width and height of the rectangle.

Now we can implement an alternate representation of a rectangle and show that we can use the same procedures for perimeter and area. The easiest will be the second pictured above, where we represent a rectangle by a single point and its width and height.
; rectangle constructor; combine a point, a width, and a height(define (make-rect a w h) (cons a (cons w h))); rectangle selectors(define (rect-width r)   (car (cdr r)))(define (rect-height r)   (cdr (cdr r)))

Using the new constructor and selectors we can test that the old rect-perimeter and rect-area procedures work unchanged.
> (define a (make-point 0 0))> (define r (make-rect a 2 10))> (display (rect-perimeter r))24> (display (rect-area r))20

The box-and-pointer diagram of this rectangle reveals that the elements are laid out exactly the same way internally, but the rectangle is different conceptually.

This time the rectangle is made up of a point, a width, and a height. The corresponding rect-width and rect-height procedures access their values directly rather than computing them.

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

Tim Kington said...

I don't understand the first rect-width and rect-height functions. Where are a and b coming from?

Bill the Lizard said...

Tim,
The rectangle is made up of two points (a and b) that I create before calling make-rect. I was a little bit lazy in my implementation. I could have defined make-rect to take the two x and two y values as primitives, then build the two points internally. Instead I defined it to take two points (defined in the previous exercise) that are already instantiated.

I added a couple of box-and-pointer diagrams to the post that will hopefully make it more clear how the two different rectangles are put together.

Tim Kington said...

I get the way you're building rectangles. It's the scoping I'm not sure about. Maybe there's something going on here that I don't see, but it seems to me that a and b are undefined here:

; rectangle selectors
(define (rect-width r)
(abs (- (x-point a) (x-point b))))

Shouldn't it be something like:

(define (rect-width r)
(abs (- (x-point (car r))...

Bill the Lizard said...

Time,
D'oh! I get you now. I was wondering why you were asking such an easy question, but I thought maybe you were being Socratic. I should have realized that I just needed to look a little harder. :)

Yes, that's right, I needed to get the car and cdr of r in the rect-width and rect-height procedures. I've fixed that now, and I'm not really sure how I got this to run in the first place. I copied the old code from here into a fresh interpreter window and it didn't work. I know it worked before because I always copy the output from the interpreter into my post. The only way I can think that the old code would have worked is if I had somehow defined a and b outside the scope of the two procedures that were using them incorrectly.

Anyway, thanks a lot for the correction. I'll try to avoid making this same mistake in the future by getting in the habit of changing variable names between different scopes.

Josh Nahum said...

The specification never said the rectangle needed to be aligned with the grid. It isn't to much of a challenge to allow all possible rectangles (even those with some rotation).