SICP. 2.1–2.1.2
2023-03-01 Wed

We can abstract not only with procedures, but also with (compound) data. The notion for the latter is called data abstraction.

Using data abstraction, systems are divided into two parts. There is a part that uses data and there is a part that defines data.

The part that uses data makes no assumptions about the data that are not necessary for the task at hand. We say that this part operates on ``abstract data''.

The part that defines the data does so in a way which is independent from the way data will be used by the other part of the system. We say that the defining-data part defines a ``concrete'' data representation.

The interface between the two parts consists of a set of two kinds procedures. We call them selectors and constructors.

Let us exemplify the idea of data abstraction using rational numbers.

A rational number is an entity made of a numerator and a denominator.

We don't have, at the moment, a way to construct a rational number, given a numerator and a denominator. But suppose we assume we do. Not only that. We are also going to assume that given a rational number, we have a way to extract the numerator and a way to extract the denominator; and that we have a procedure for each of those three things (make-rat — the constructor —, numer, and denom — the selectors).

Even without implementing those procedures, we can express in terms of them the procedurs for adding, subtracting, etc.:

(define (add-rat x y)
  (make-rat (+ (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))

(define (sub-rat x y)
  (make-rat (- (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))

(define (mul-rat x y)
  (make-rat (* (numer x) (numer y))
            (* (denom x) (denom y))))

(define (div-rat x y)
  (make-rat (* (numer x) (denom y))
            (* (denom x) (numer y))))

(define (equal-rat? x y)
  (= (* (numer x) (denom y))
     (* (numer y) (denom x))))

We have said that a rational number is an entity made of two things. But how do we make a thing made of two things? It turns out that Scheme provides us with a procedure that allows us to stick two things together into a pair. I'm talking of the magical cons. Once you have made with pair with cons, you can extract the first element with car and the second element with cdr. Data objects constructed from pairs are called list-structured data.

So, here is what we can do:

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

Actually better:

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

Exercise:

Define a better version of make-rat that handles both positive and negative arguments. Make-rat should normalize the sign so that if the rational number is positive, both the numerator and denominator are positive, and if the rational number is negative, only the numerator is negative.

Answer:

(define (make-rat n d)
  (let ((g (gcd n d)))
    (if (or (and (> n 0) (> d 0))
            (and (< n 0) (< d 0)))
        (cons (/ (abs n) (abs g)) 
              (/ (abs d) (abs g)))
        (cons (- (/ (abs n) (abs g)))
              (/ (abs d) (abs g))))))

(print-rat (make-rat 2 4))  ;; =>  1/2  
(print-rat (make-rat -2 4)) ;; => -1/2
(print-rat (make-rat 2 -4)) ;; => -1/2

In general, the underlying idea of data abstraction is to identify for each type of data object a basic set of operations in terms of which all manipulations of data objects of that type will be expressed, and then to use only those operations in manipulating the data.

We can think of a system in which data abstraction is employed as divided into levels by ``abstraction barriers''. Above one abstraction barrier there is a level which includes those programs that use the the data abstraction which is implemented by those programs in the level below the barrier.

Here is how we can represent the structure of the rational-number system:

   *Figure 2.1:* Data-abstraction barriers in the rational-number
   package.

                +------------------------------------+
        --------| Programs that use rational numbers |--------
                +------------------------------------+
                  Rational numbers in promblem domain
                    +---------------------------+
        ------------|   add-rat  sub-rat  ...   |-------------
                    +---------------------------+
           Rational numbers as numerators and denominators
                      +------------------------+
        --------------| make-rat  numer  denom |--------------
                      +------------------------+
                      Rational numbers as pairs
                          +----------------+
        ------------------| cons  car  cdr |------------------
                          +----------------+
                    However pairs are implemented

(Figure from SICP Unofficial Texinfo Format version 2.neilvandyke4 (January 10, 2007))

This simple idea has many advantages…

Exercise:

Consider the problem of representing line segments in a plane. Each segment is represented as a pair of points: a starting point and an ending point. Define a constructor make-segment and selectors start-segment and end-segment that define the representation of segments in terms of points. Furthermore, a point can be represented as a pair of numbers: the \(x\) coordinate and the \(y\) coordinate. Accordingly, specify a constructor make-point and selectors x-point and y-point that define this representation. Finally, using your selectors and constructors, define a procedure midpoint-segment that takes a line segment as argument and returns its midpoint (the point whose coordinates are the average of the coordinates of the endpoints). To try your procedures, you’ll need a way to print points:

(define (print-point p)
  (newline)
  (display "(")
  (display (x-point p))
  (display ",")
  (display (y-point p))
  (display ")"))

Answer:

;; constructor
(define (make-segment s e) (cons s e))
;; selectors
(define (start-segment x) (car x))
(define (end-segment x) (cdr x))

;; constructor
(define (make-point x y) (cons x y))
;; selectors
(define (x-point x) (car x))
(define (y-point x) (cdr x))

(define (mid-point-segment line)
  (make-point (/ (+ (x-point (start-segment line))
                    (x-point (end-segment line)))
                 2)
              (/ (+ (y-point (start-segment line))
                    (y-point (end-segment line)))
                 2)))

(define (print-point p)
  (newline)
  (display "(")
  (display (x-point p))
  (display ",")
  (display (y-point p))
  (display ")"))

(print-point (mid-point-segment (make-segment (make-point 2 2) (make-point 6 4))))

Exercise:

Implement a representation for rectangles in a plane. (Hint: You may want to make use of Exercise 2.2.) In terms of your constructors and selectors, create procedures that compute the perimeter and the area of a given rectangle. Now implement a different representation for rectangles. Can you design your system with suitable abstraction barriers, so that the same perimeter and area procedures will work using either representation?

Answer:

I'm assuming the sides of the rectangle and the axes are parallel.

Sides are represented by segments whose points whose order is clockwise, E.g., left-side: (bottom-point . top-point), top-side: (left-point . right-point).

• 1st representation:

(define (make-rec left-side top-side)
  (cons left top))

(define (length rec)
  (let ((top-left-point (cdr (car rec)))
        (top-right-point (car (cdr rec))))
    (abs (- (x-point top-right-point)
            (x-point top-left-point)))))

(define (width rec)
  (let ((bottom-left-point (car (car rec)))
        (top-left-point (cdr (car rec))))
    (abs (- (y-point top-left-point)
            (y-point bottom-left-point)))))

• 2nd representation:

(define (make-rec right-side bottom-side)
  (cons right-side bottom-side))

(define (length rec)
  (let ((bottom-left-point (cdr (cdr rec)))
        (bottom-right-point (car (cdr rec))))
    (abs (- (x-point bottom-right-point)
            (x-point bottom-left-point)))))

(define (width rec)
  (let ((top-right-point (car (car rec)))
        (bottom-right-point (car (cdr rec))))
    (abs (- (y-point top-right-point)
            (y-point bottom-right-point)))))

• Procedures which work with both representations:

(define (perimeter rec)
  (* 2
     (+ (length rec) (width rec))))

(define (area rec)
  (* (length rec) (width rec)))