Data Abstraction

Abelson & Sussman · 1996 · SICP §2.1

Separate how data is used from how it's represented. Constructors and selectors form an abstraction barrier. You can even implement pairs with nothing but functions.

Rational numbers — make-rat, numer, denom

A rational number is a pair: numerator and denominator. The constructor make-rat and selectors numer, denom define the interface. Everything above the barrier uses only these three operations.

Scheme

; Rational number arithmetic via abstraction barriers.

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

(define (numer x) (car x))
(define (denom x) (cdr x))

(define (print-rat x)
  (display (numer x))
  (display "/")
  (display (denom x))
  (newline))

; Arithmetic uses only numer, denom, make-rat:
(define (add-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 one-half (make-rat 1 2))
(define one-third (make-rat 1 3))

(display "1/2 + 1/3 = ") (print-rat (add-rat one-half one-third))
(display "1/2 * 1/3 = ") (print-rat (mul-rat one-half one-third))
(display "1/3 + 1/3 = ") (print-rat (add-rat one-third one-third))

Abstraction barriers

The rational number layer never touches cons, car, cdr directly. The programs that use rationals never touch numer or denom directly — they use add-rat, mul-rat. Each layer talks only to the layer below it. Change the representation, and only one layer needs updating.

Scheme

; Barrier discipline: swap the representation,
; nothing above the barrier changes.

; Representation 1: reduce on construction
(define (make-rat-v1 n d)
  (let ((g (gcd (abs n) (abs d))))
    (cons (/ n g) (/ d g))))
(define (numer-v1 x) (car x))
(define (denom-v1 x) (cdr x))

; Representation 2: reduce on access
(define (make-rat-v2 n d) (cons n d))
(define (numer-v2 x)
  (let ((g (gcd (abs (car x)) (abs (cdr x)))))
    (/ (car x) g)))
(define (denom-v2 x)
  (let ((g (gcd (abs (car x)) (abs (cdr x)))))
    (/ (cdr x) g)))

; Both produce the same results:
(define r1 (make-rat-v1 6 8))
(define r2 (make-rat-v2 6 8))

(display "v1: ") (display (numer-v1 r1)) (display "/") (display (denom-v1 r1)) (newline)
(display "v2: ") (display (numer-v2 r2)) (display "/") (display (denom-v2 r2))
; Both print 3/4

What is data? — procedural representation of pairs

The deepest insight in this chapter: you can implement cons, car, and cdr with nothing but lambda. Data isn't a thing stored in memory — it's any set of constructors and selectors that satisfies the contract: (car (cons x y)) = x and (cdr (cons x y)) = y.

Scheme

; Pairs implemented with nothing but procedures.
; No data structures — just closures.

(define (my-cons x y)
  (lambda (m)
    (cond ((= m 0) x)
          ((= m 1) y)
          (else (error "Argument not 0 or 1")))))

(define (my-car z) (z 0))
(define (my-cdr z) (z 1))

; Test the contract:
(define p (my-cons 3 7))

(display "(car (cons 3 7)) = ")
(display (my-car p)) (newline)

(display "(cdr (cons 3 7)) = ")
(display (my-cdr p)) (newline)

; Nest them — pairs of pairs:
(define nested (my-cons (my-cons 1 2) (my-cons 3 4)))
(display "car(car(nested)) = ")
(display (my-car (my-car nested))) (newline)
(display "cdr(cdr(nested)) = ")
(display (my-cdr (my-cdr nested)))

Interval arithmetic

Another data abstraction: intervals with upper and lower bounds. Same pattern — constructors, selectors, and operations that respect the barrier. The operations propagate uncertainty: the result interval contains all possible values.

Scheme

; Interval arithmetic: another abstraction barrier.

(define (make-interval a b) (cons a b))
(define (lower-bound x) (car x))
(define (upper-bound x) (cdr x))

(define (add-interval x y)
  (make-interval (+ (lower-bound x) (lower-bound y))
                 (+ (upper-bound x) (upper-bound y))))

(define (mul-interval x y)
  (let ((p1 (* (lower-bound x) (lower-bound y)))
        (p2 (* (lower-bound x) (upper-bound y)))
        (p3 (* (upper-bound x) (lower-bound y)))
        (p4 (* (upper-bound x) (upper-bound y))))
    (make-interval (min p1 p2 p3 p4)
                   (max p1 p2 p3 p4))))

(define (print-interval x)
  (display "[")
  (display (lower-bound x))
  (display ", ")
  (display (upper-bound x))
  (display "]")
  (newline))

(define a (make-interval 2.0 2.2))
(define b (make-interval 3.0 3.1))

(display "a + b = ") (print-interval (add-interval a b))
(display "a * b = ") (print-interval (mul-interval a b))

Notation reference

Scheme	Python	Meaning
(cons a b)	(a, b)	Construct a pair
(car p)	p[0]	First element
(cdr p)	p[1]	Second element
(gcd a b)	math.gcd(a, b)	Greatest common divisor
(error "msg")	raise ValueError("msg")	Signal an error

Neighbors

Translation notes

Scheme's cons/car/cdr are primitive; Python uses tuples or lists. The procedural pairs example (section 3) shows that the distinction is superficial — closures suffice. Python's gcd lives in math; Scheme's is typically built in. The interval arithmetic section foreshadows the "dependency problem" that SICP poses as an exercise: algebraically equivalent expressions give different interval widths because repeated variables are treated as independent. That subtlety is omitted here but worth exploring.

Ready for the real thing? Read SICP §2.1.

← Higher-Order Functions by june.kim Hierarchical Data · 5 of 22 →