Sunday, September 25, 2011

SICP 2.46 - 2.48: Frames & Painters

From SICP section 2.2.4 Example: A Picture Language

A frame can be described by three vectors -- an origin vector and two edge vectors. The origin vector specifies the offset of the frame's origin from some absolute origin in the plane, and the edge vectors specify the offsets of the frame's corners from its origin. If the edges are perpendicular, the frame will be rectangular. Otherwise the frame will be a more general parallelogram. A two-dimensional vector v running from the origin to a point can be represented as a pair consisting of an x-coordinate and a y-coordinate.

Exercise 2.46 asks us to implement a data abstraction for vectors by giving a constructor make-vect and corresponding selectors xcor-vect and ycor-vect. In terms of these selectors and constructor, we'll also implement procedures add-vect, sub-vect, and scale-vect that perform the operations for vector addition, vector subtraction, and multiplying a vector by a scalar:

(x1, y1) + (x2, y2) = (x1 + x2, y1 + y2)
(x1, y1) - (x2, y2) = (x1 - x2, y1 - y2)
s * (x, y) = (sx, sy)

The solution for the constructor and selectors uses cons, car, and cdr in the same pattern we've seen at least a dozen times by now.
(define (make-vect x y)   (cons x y))(define (xcor-vect v)   (car v))(define (ycor-vect v)   (cdr v))

Once we have those procedures in place, we can use them to build the vector operations specified.
(define (add-vect u v)   (make-vect     (+ (xcor-vect u) (xcor-vect v))     (+ (ycor-vect u) (ycor-vect v))))(define (sub-vect u v)   (make-vect     (- (xcor-vect u) (xcor-vect v))     (- (ycor-vect u) (ycor-vect v))))(define (scale-vect s v)   (make-vect     (* s (xcor-vect v))     (* s (ycor-vect v))))

We can test these procedures out with a few known values before moving on to the next step.
> (define u (make-vect 2 4))> u(2 . 4)> (define v (make-vect 3 1))> v(3 . 1)> (define w (add-vect u v))> w(5 . 5)> (define x (sub-vect w u))> x(3 . 1)> (define y (scale-vect 3 w))> y(15 . 15)

Exercise 2.47 gives us the following constructors for frames, one using list and the other using cons:
(define (make-frame origin edge1 edge2)   (list origin edge1 edge2))(define (make-frame origin edge1 edge2)   (cons origin (cons edge1 edge2)))

We're asked to supply the appropriate selectors to produce an implementation for frames for each of the two constructors. Like any selector implementation, the task here is simply to extract each piece from the assembled object. We'll follow the naming convention from the previous exercise and call our selectors origin-frame, edge1-frame, and edge2-frame. Let's start with the version that uses list.
; 2.47a(define (make-frame origin edge1 edge2)   (list origin edge1 edge2))(define (origin-frame frame)   (car frame))(define (edge1-frame frame)   (car (cdr frame)))(define (edge2-frame frame)   (car (cdr (cdr frame))))

The selectors simply use the right combinations of car and cdr to extract the appropriate elements from the list. We can test it with some of the same values used in the previous exercise, but we'll need to add an origin vector.
> (define f (make-frame (make-vect 0 0) (make-vect 2 4) (make-vect 3 1)))> f((0 . 0) (2 . 4) (3 . 1))> (origin-frame f)(0 . 0)> (edge1-frame f)(2 . 4)> (edge2-frame f)(3 . 1)

Because the internal representation of a frame is different in the second implementation of make-frame, one of the selectors will have to change for the second part of the exercise. The original origin-frame and edge1-frame implementations will still work, but the edge2-frame procedure causes an error if you try to use it.
; 2.47b(define (make-frame origin edge1 edge2)   (cons origin (cons edge1 edge2)))(define (edge2-frame frame)   (cdr (cdr frame)))

Run exactly the same test from above to verify that you get the same results (except for the internal structure of the frame in the second step).
> (define f (make-frame (make-vect 0 0) (make-vect 2 4) (make-vect 3 1)))> f((0 . 0) (2 . 4) 3 . 1)> (origin-frame f)(0 . 0)> (edge1-frame f)(2 . 4)> (edge2-frame f)(3 . 1)

Exercise 2.48 asks us to define a representation for segments using our vector representation from exercise 2.46 above. We'll need to define the constructor make-segment and the selectors start-segment and end-segment.
(define (make-segment v1 v2)   (cons v1 v2))(define (start-segment segment)   (car segment))(define (end-segment segment)   (cdr segment))

Again, these use the same pattern we've seen before. In the next exercise, we'll take a closer look at the procedures above by drawing pictures with line segments using The SICP Picture Language package.

Related:

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