Compound Data

Table of Contents

1 Layers

Abstraction layers create barriers that isolate the details of the lower layers.

(define (+rat x y)
   (+ (* (numer x) (denom y))
      (* (numer y) (denom x)))
   (* (denom x) (denom y))))
(define (*rat x y)
   (* (numer x) (numer y))
   (* (denom x) (denom y))))

make-rat is a constructor. numer and denom are selectors.

Programming languages should express the concepts in our heads. Otherwise, they confuse not only our programming, but also our minds.

"Why bother with data abstraction?" is a similar question to "why bother to package instructions up into procedures?"

2 Pairs

The glue that holds data together is called list structure. It provides a way to create pairs.

cons constructs a pair whose first part is x and whose second part is y.

(cons x y)

car selects the first part of the pair p.

(car p)

cdr selects the second part of the pair p.

(cdr p)

Pairs can be reprented using box and pointer notation. (Note: this term and representation appears to be defunct.)

(define (make-rat n d)
  (cons n d))
(define (numer x) (car x))
(define (denom x) (cdr x))

The above implementation spits out 1 2 + 1 4 = 6 8 1 2 1 4 6 8 \frac{1}{2}+\frac{1}{4}=\frac{6}{8} . How can this be rectified?

(define (make-rat n d)
  (let ((g (gcd n d)))
    (cons (/ n g)
          (/ d g))))

let creates a local context for local names.

3 Data abstraction

USE:                     +rat *rat -rat
ABSTRACTION LAYER:    make-rat numer denom
REPRESENTATION:              pairs

Set up data objects by postulating constructors and selectors to separate use from representation. If you have the name of a spirit, you have control over it.

Another way of representing rationals:

(define (make-rat n d) (cons n d))
(define (numer x)
  (let ((g (gcd (car x) (cdr x))))
    (/ (car x) g)))
(define (denom x)
  (let ((g (gcd (car x) (cdr x))))
    (/ (cdr x) g)))

There is a narrow line between deferring decisions and outright procrastination. Ideally, we can make progress without having to be bound by the consequences of our decisions. Through wishful thinking, we give names to our decisions, and continue as if we've made a decision. Wishful thinking is a powerful design technique.

The maxim "do all of your design before any of your code" was likely to be coined by someone who has rarely implemented complex computer systems.

Computer science is a lot like magic; there's a bad part of computer science which is a lot like religion.

The real power is that you can pretend you've made the decision, then later on figure out what decision you ought to have made. When you can do that, you have the best of both worlds.

4 Descartes

One beauty of abstraction is the ability to use abstract data as building blocks for even more complicated things.

; representing vectors in the plane
(define (make-vector x y) (cons x y))
(define (xcor p) (car p))
(define (ycor p) (cdr p))

Build line segments from vectors.

; representing line segments
(define (make-seg p q) (cons p q))
(define (seg-start s) (car s))
(define (seg-end s) (cdr s))
(define (midpoint s)
  (let ((a (seg-start s))
        (b (seg-end s)))
     (average (xcor a) (xcor b))
     (average (ycor a) (ycor b)))))
(define (length s)
      ((dx (- (xcor (seg-end s))
              (xcor (set-start s))))
       (dy (- (ycor (seg-end s))
              (ycor (set-start s)))))
    (sqrt (+ (square dx) (square dy)))))

How segments, vectors and pairs are abstracted:

make-seg seg-start seg-end
make-vector xcor ycor

Closed means of abstraction allows for pairs of pairs. Abstractions keep complexity from sprawling out and allow choices to be localised. Abstract data can sit on top of any suitable representation.

5 Turtles all the way down

rational numbers

What is a rational number? It is a number that satisfies the axiom:

If x = (make-rat n d) 𝑥 (make-rat n d) x=\texttt{(make-rat n d)} Then (numer x) (denom x) = n d (numer x) (denom x) 𝑛 𝑑 \frac{\texttt{(numer x)}}{\texttt{(denom x)}}=\frac{n}{d}

What is a pair? It is a thing that satisifes the axiom:

For any x and y,
(car (cons x y)) is x
(cdr (cons x y)) is y.

Using this logic, we can proceed to build pairs from thin air.

(define (cons a b)
  (lambda (pick)
    (cond ((= pick 1) a)
          ((= pick 2) b))))
(define (car x) (x 1))
(define (cdr x) (x 2))

We have just built data out of a procedure - built out of existential nothing.

We don't need data to build these data abstractions, because we can do everything in terms of procedures.

We will continue to blur the line between data and procedures. A procedure is not just the act of doing something; a procedure is a real object that exists.