Section 2.1: Intro Data Abstraction

Notes from Book section 2.1 and Youtube lecture 2B.

Compound data. So far we've been operating on numbers for a lack of other data types to work on. This chapter introduces data. The basic datatype in Scheme is the pair.

Make pairs with cons.

(cons x y) -> pair (x, y)

Retrieve the first element with car. Retrieve the second element with cdr.

(car (cons x y)) -> x

(cdr (cons x y)) -> y

This is true for any x and y, even if x and y are themselves pairs. The ability to combine not just primitives (like numbers) but also compound data is called closure. Pairs would be limited an uninteresting if we could only crate them with a limited set of primitive data.

Suppose you have a data type of point, defined as a pair created by cons.

(define (make-point x y) (cons x y))

(define (x-coordinate p) (car p))

(define (y-coordinate p) (cdr p))

You can combine the points into a pair to define the endpoints of a line segment...

(define (make-segment a b) (cons a b))

(define (start-segment s) (car s))

(define (end-segmenet s) (cdr s))

...and then define computations based on the points.

(define (midpoint s)
    (make-point (average (x-coordinate (start-segment))
                         (x-coordinate (end-segment)))
                (average (y-coordinate (start-segment))
                         (y-coordinate (end-segment)))))

This definition also make a layered approach to the problem of lines, something like this:

Segments
------------
make-seg, seg-start, seg-end
------------
Points
------------
make-point, x-coordinate, y-coordinate
------------
Pairs, Numbers

The definition of points could change, and as long as the constructors and accessors make-point, x-coordinate, y-coordinate are updated to match the new definition, the line segment procedures don't need to change.

The pair data structure can be represented as procedures:

(define (cons x y)
    (lambda (pick)
        (cond ((= pick 1) x)
              ((= pick 2) y))))

(define (car z) (z 1))

(define (cdr z) (z 2))

Mind-blowing! There is no data, just procedures. Still, it's a valid representation of pairs because it fulfills the contract

(car (cons a b)) -> a

(cdr (cons a b)) -> b

So in some sense you can build data abstractions without data.