SICP Exercise 2.47: Frames

Here are two possible constructors for frames:

(define (make-frame origin edge1 edge2)
  (list origin edge1 edge2))

(define (make-frame origin edge1 edge2)
  (cons origin (cons edge1 edge2)))

For each constructor supply the appropriate selectors to produce an implementation for frames.

First, let's look at the structures the two constructors produce.

The first (list-based) version of make-frame constructs a list of origin, edge1 and edge2 in that order. As shown in section 2.2.1, a list is really represented as a chain of pairs with each pair consisting of the next element in the list and the next pair in the chain (with the last pair having nil as its second element. This means that the list constructed is a chain of three pairs where the first components of each pair are origin, edge1 and edge2 respectively. I.e. The second (pair-based) version of make-frame also constructs a chain of pairs, but in this case it is done directly and only consists of two pairs. The first pair has origin as its first component and the second pair as its second component. The second pair has edge1 as its first component and edge2 as its second component. I.e. As can be seen, the two structures differing only in the way edge2 is included in them. This means that selectors origin-frame and edge1-frame will be identical regardless of the constructor implementation used. The former simply returns the first element of the root pair via car, while the latter returns the first element of the second pair in the structure via cadr:

(define (origin-frame f) (car f))
(define (edge1-frame f) (cadr f))

The only difference is in the implementations of edge2-frame. In the list-based representation we need this selector to return the first element of the third pair. I.e. via caddr:

(define (edge2-frame f) (caddr f))

However, in the pair-based representation we need this selector to return the second element of the second pair. I.e. via cddr:

(define (edge2-frame f) (cddr f))

The choice as to which we we use is fairly arbitrary. It could be argued that the pair-based representation is more compact, eliminating the third pair. However the list-based representation feels more elegant.

Anyway, here they are in use. First the list-based representation:

> (define (make-frame origin edge1 edge2)
    (list origin edge1 edge2))
> (define (origin-frame f) (car f))
> (define (edge1-frame f) (cadr f))
> (define (edge2-frame f) (caddr f))

> (define origin (make-vect 10 5))
> (define edge1 (make-vect 0 100))
> (define edge2 (make-vect 40 -4))

> (define frame (make-frame origin edge1 edge2))

> (origin-frame frame)
'(10 . 5)
> (edge1-frame frame)
'(0 . 100)
> (edge2-frame frame)
'(40 . -4)

...and the pairs-based representation:

> (define (make-frame origin edge1 edge2)
    (cons origin (cons edge1 edge2)))
> (define (origin-frame f) (car f))
> (define (edge1-frame f) (cadr f))
> (define (edge2-frame f) (cddr f))

> (define origin (make-vect 10 5))
> (define edge1 (make-vect 0 100))
> (define edge2 (make-vect 40 -4))

> (define frame (make-frame origin edge1 edge2))

> (origin-frame frame)
'(10 . 5)
> (edge1-frame frame)
'(0 . 100)
> (edge2-frame frame)
'(40 . -4)

As you'd expect, although the internal representations differ, the constructor and selectors hide this from the next layer of abstraction up and so they behave identically.

SICP Exercise 2.46: Vectors

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. Implement a data abstraction for vectors by giving a constructor make-vect and corresponding selectors xcor-vect and ycor-vect. In terms of your selectors and constructor, implement procedures add-vect, sub-vect, and scale-vect that perform the operations 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)

As a two-dimensional vector has only two pieces of data associated with it, the x- and y-coordinates, it lends itself naturally to being represented as a pair. Let's put x as the first elements, and y as the second. We can then access them via car and cdr respectively:

(define (make-vect x y) (cons x y))
(define (xcor-vect v) (car v))
(define (ycor-vect v) (cdr v))

Given this representation (or at least this constructor and these selectors), we can implement the given operations straightforwardly. We simply need to extract the x- and y-coordinates from the vectors we're dealing with using the selectors, perform the appropriate mathematical operations on them and then create a new vector as our result using the constructor:

(define (add-vect v1 v2)
  (make-vect (+ (xcor-vect v1) (xcor-vect v2))
             (+ (ycor-vect v1) (ycor-vect v2))))

(define (sub-vect v1 v2)
  (make-vect (- (xcor-vect v1) (xcor-vect v2))
             (- (ycor-vect v1) (ycor-vect v2))))

(define (scale-vect s v)
  (make-vect (* s (xcor-vect v))
             (* s (ycor-vect v))))

Let's see them in action:

> (define v1 (make-vect 4 5))
> (define v2 (make-vect 7 3))

> v1
'(4 . 5)
> v2
'(7 . 3)

> (xcor-vect v1)
4
> (ycor-vect v1)
5
> (ycor-vect v2)
3
> (xcor-vect v2)
7

> (add-vect v1 v2)
'(11 . 8)
> (add-vect v2 v1)
'(11 . 8)

> (sub-vect v1 v2)
'(-3 . 2)
> (sub-vect v2 v1)
'(3 . -2)

> (scale-vect 3 v1)
'(12 . 15)
> (scale-vect 2 v2)
'(14 . 6)

SICP Exercise 2.45: Splitting the splitters

Right-split and up-split can be expressed as instances of a general splitting operation. Define a procedure split with the property that evaluating

(define right-split (split beside below))
(define up-split (split below beside))

produces procedures right-split and up-split with the same behaviors as the ones already defined.

What we want split to do here is to return a procedure that takes a painter and some integer value, n that applies the supplied splitting operations in the given order. As we noted in exercise 2.44, right-split and up-split are very similar. Here they are again, but with the differences highlighted:

(define (right-split painter n)
  (if (= n 0)
      painter
      (let ((smaller (right-split painter (- n 1))))
        (beside painter (below smaller smaller)))))

(define (up-split painter n)
  (if (= n 0)
      painter
      (let ((smaller (up-split painter (- n 1))))
        (below painter (beside smaller smaller)))))

This gives us the pattern for the procedure we want split to return. We just need to replace the calls to below and beside with the appropriate calls to the supplied splitting operations. We can define this as an inner procedure for split and then return a lambda expression that invokes the procedure with the appropriate values:

(define (split large-splitter small-splitter)
  (define (splitter painter n)
    (if (= n 0)
        painter
        (let ((smaller (splitter painter (- n 1))))
          (large-splitter painter (small-splitter smaller smaller)))))
  (lambda (painter n) (splitter painter n)))

We can then use this to produce new versions of right-split and up-split:

(define right-split (split beside below))
(define up-split (split below beside))

...and then try them out. Invoking:

(right-split spiral 4)

...produces: While...

(up-split spiral 4)

...produces: