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.

6 comments:

miles said...

Hey, Bill. Just wanted to say thank you for the inspiring work. I'm not sure whether you will believe it or not, but seeing you attempt to work through all of SICP has helped me to start reading it myself. One question, though: How much time are you usually putting into the book per day or per week? I'm just curious of your methods of balancing this along with being pragmatic. Would you say that there have been any significant changes to how you approach problems now?

Thanks.

Bill the Lizard said...

Hi miles,
Thanks for commenting. It's nice to hear when someone is getting some benefit out of these posts. I work 60 hours a week (between two jobs) and I'm trying to finish a Master's degree, so I don't put in as much time each week on SICP as I'd like. Posting each exercise on here actually slows me down a lot, but it's also what motivates me to continue through the book when I reach a tough spot. I only spend a few hours each week, but it could be a lot less if I wasn't taking the time to write up each solution in a blog post. Probably the biggest change in how I work since starting SICP is that I'm starting to think more in a functional style, even when I write object-oriented code. I've also noticed that recursive solutions to problems occur to me a lot more quickly than they used to.

miles said...

Awesome! Sounds like a ton of work, though. Do you still roll out the 6.001 lectures every now and then, or have you pretty much taken everything you can from them. Also, how beneficial do you think blogging about these problems have been as opposed to if you were to just do them on your own without, in a sense, this documentation. The last thing I would like to know is where the heck you found a syntax highlighter for Scheme. I could definitely use a nudge in the right direction with where to find that, heh.

Bill the Lizard said...

miles,
It is a ton of work. I'd estimate that I spend an extra 30 to 60 minutes on each exercise because I blog them. I do still watch the lectures. I'll post all of my notes, but I'm trying to post those so they match up with the material in the exercises. I think most people could get a lot out of the book if they just read it and did the exercises normally. I've noticed that I can really get myself to understand a topic really thoroughly when I try to explain it to someone else, though, so writing up the blog posts is a good practice for me, even if it does take up a lot of time. That's not actually a Scheme-specific code format. I just use Format My Source Code for Blogging. I'd love to find one that highlights keywords.

Micky said...

Hey Bill.

I can't seem to get my head around the implementation of frames in SICP.

The book states
> We will use coordinates in the unit square (0< x,y< 1) to specify images

How are images expressed as coordinates? The only interpretation I can muster is that all images, being lines, can only be mapped to a frame whose boundary can not exceed that of a unit square. But I doubt that because the next line in the book, explaining a "frame coordinate map", says

> The map transforms the unit square into the frame by mapping the vector v = (x,y) to the vector sum Origin(Frame) + x*Edge1(Frame) + y*Edge2(Frame)

The vector (0,0) being mapped to the origin of the frame and (1,1) to the vertex diagonally opposite the origin, only adds to my confusion. What are these vectors? The origin of the image or what?

I can't make sense of this and it's preventing me from moving further into the text as everything discussed after builds on this concept. I'd find it very helpful if I could get a detailed explanation of how you understood this idea.

Bill the Lizard said...

If anyone else has the same question as Micky above, you can see my answer on Stack Overflow: How frames are used in the picture language in SICP.