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.