Quirksand

SICP

SICP 2.1.2 Solutions

January 30, 2014 18:48

Ex 2.2.

Certainly there are any number of ways to represent a line segment that is defined by two points, but the problem statement itself practically gives the suggestion of using a pair. Which is probably the simplest, and works well for our requirements. Points, as well, can be stored in the same fashion, especially as they are intended to be defined by two Cartesian coordinates.

Although the selectors give the impression that a segment is possibly directed (with start-segment and end-segment) there isn’t anything in the requirements that depends on that information. Getting the midpoint as a point ought to be the same regardless of which way the segment is ‘pointing’, and indeed one of the tests I added checks for just that.

Ex 2.3.

This time we’re tasked with developing two distinct representations for rectangles. This problem is fairly open-ended, and although the use of segments is suggested, it is by no means required. It’s better to focus on creating the abstraction barriers. Doing this here is a matter of creating suitable selectors that the perimeter and area routines can use, without needing to have deeper knowledge of the rectangles ‘internal’ storage details. My additional tests delve into some of the details that might differentiate the implementations, but as always they are optional, and there are likely other details that I did not even consider.

The selectors I used in the calculation routines were rect-length and rect-width. These are sensible for using in similar math routines. Although, in somewhat similar fashion to the idea of a ‘directed’ segment, there’s no actual need for the area or perimeter to know that the ‘length’ is greater than or equal to the ‘width’. All they really need are two different sides.

My first implementation uses only two points, the corners to determine a rectangle. Then the rectangle can be stored as a simple pair of points. There is the use of ‘internal’ selectors corner-1 and corner-2 which pick the respective points. They would be considered ‘internal’ in that a selector used by higher level procedures such as rect-length should not make use of them, even if they are technically available. Abstraction barriers are in many cases something that needs to be enforced by the program designer, although many languages can assist in keeping them from breaking.

(define (make-rect c1 c2)
  (cons c1 c2)
  )

(define (corner-1 r) (car r))
(define (corner-2 r) (cdr r))

(define (rect-length r)
  (let ((side-X (abs (- (x-point (corner-1 r)) (x-point (corner-2 r)))))
        (side-Y (abs (- (y-point (corner-1 r)) (y-point (corner-2 r)))))
        )
    (if (> side-Y side-X)
        side-Y
        side-X
        )
    )
  )

(define (rect-width r)
  (let ((side-X (abs (- (x-point (corner-1 r)) (x-point (corner-2 r)))))
        (side-Y (abs (- (y-point (corner-1 r)) (y-point (corner-2 r)))))
        )
    (if (< side-Y side-X)
        side-Y
        side-X
        )
    )
  )

This approach uses a small amount of storage space, but it does have a potential problem. It can only be used to define rectangles that are oriented to the x and y axis in the plane. Defining them with just two points implies that the other sides are orthogonal by necessity. That might work well in many systems, so I don’t consider it a big failing, just a limitation.

This one makes use of two segments (as in 2.2) that indicate the sides of the rectangle. Note that the amount of code is almost exactly the same as in the first one.

(define (seg-length seg)
  (sqrt (+ (sqr(- (x-point (start-segment seg)) (x-point (end-segment seg))))
           (sqr(- (y-point (start-segment seg)) (y-point (end-segment seg))))
           )
        )
  )

(define (make-rect x-seg y-seg)
   (let ((x-len (seg-length x-seg))
         (y-len (seg-length y-seg))
         )
      (if (> x-len y-len)
          (cons x-seg y-seg)
          (cons y-seg x-seg)
          )
    )
  )

(define (rect-length r) 
  (seg-length (car r))
  )

(define (rect-width r) 
  (seg-length (cdr r))
  )

This time we can build the idea of ‘length’ and ‘width’ directly into the structure by determining which is which in the constructor. It actually involves a slightly more complicated calculation, but it should be obvious that this now allows for rotated rectangles. Another advantage is that this calculation only needs to performed once, whereas in the first representation it had to be done every time the length was requested.

What’s happened here is that I’ve tailored the second representation a bit to match how I designed the area and perimeter functions. Knowing that length and width will be required gave me some impetus to optimize the rectangle data structure to that end. In this case the abstraction barrier still exists, but to a certain amount I’ve allowed it to leak a bit. Personally, I don’t see this as all that terrible, as long as it’s understood that the system as a whole might need to be adjusted. It’s a sign of the fact that all abstractions eventually leak, as Joel Spolsky famously expounded on. Not to discount what’s being taught in this book — it is important to understand what is useful about the barrier before understanding what might happen if they do leak.

Solutions 2.1.2