Data Abstraction and Church Numerals

Earlier, we built many abstractions around procedures. Data can likewise be organized into layers of abstraction to make complex functionality easier to design.

For example, we can define an abstract data type for rational numbers, represented as fractions:

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

We can also define common operations such as addition, subtraction, multiplication, division, and equality:

(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))))

These procedures establish an abstraction barrier. An application using rational numbers does not need to care about anything below it. There are actually several layers here:

Program Level of abstraction
Top-level application
add-rat, sub-rat … Treat a rational number as a single abstract entity
make-rat, number, denom … Treat a rational number as a numerator and denominator
cons, car, cdr … Treat a rational number as a pair

This illustrates the general approach to constructing abstract data: create a layer of constructors and selectors, such as make-rat and numer, then have the higher-level procedures exposed to applications call them.

Our abstract data type here is based on the mathematically existing concept of a rational number. But we could just as well define an abstract data type without such a real-world concept behind it. What we call “data” is, in effect, a set of constructors and selectors satisfying a specified concept. An abstract data type therefore only needs to satisfy the requirements placed on those constructors and selectors. What it actually is underneath does not matter.

For Scheme’s pair, for example, we assume that cons can construct it and that car and cdr can select its parts. We can implement this entirely with procedures, without an actual data structure:

(define (cons x y)
  (define (dispatch m)
    (cond ((= m 0) x)
	  ((= m 1) y)
	  (else
	   (error "Argument not 0 or 1:
		   CONS" m))))
  dispatch)
(define (car z) (z 0))
(define (cdr z) (z 1))

There is thus no clear boundary between data and procedures: data can consist entirely of procedures. An even more striking example is the Church numerals, invented by Alonzo Church. Everything in lambda calculus is a function, so Church encoded natural numbers as functions to introduce data into it.

First define zero: a function taking f and x and returning x directly:

(define zero (lambda (f) (lambda (x) x)))

One takes the same two arguments but returns f(x); two returns f(f(x)), and so on:

(define one (lambda (f) (lambda (x) (f x))))
(define two (lambda (f) (lambda (x) (f (f x)))))
(define three (lambda (f) (lambda (x) (f (f (f x))))))

A Church numeral’s value is the number of times f is applied. It is therefore natural to define adding one as applying f one more time:

(define add-1 (lambda (n)
		(lambda (f)
		  (lambda (x) (f ((n f) x))))))

Adding two numerals applies one numeral to the result of the other:

(define add (lambda (a b)
	      (lambda (f)
		(lambda (x) ((a f) ((b f) x))))))

The Closure Property and Conventional Interfaces

In Chapter 1, we used higher-order procedures to express a concept, then passed different procedures as arguments to produce different computations sharing that concept. This was possible because procedures themselves could be passed as arguments.

Data can have an analogous property. A pair constructed with cons, for example, can contain a reference to another pair, as in (cons 1 (cons 2 3)). The ability for an element of a data structure to itself be a structure of the same kind is called the closure property.

When we need to join more elements, we can use this property to construct a list from pairs. A more uniform convention than the example above is to let car always hold an element and cdr always point to the next pair, ending with nil:

(cons 1 (cons 2 (cons 3 (cons 4 nil))))

This structure is called a list. Scheme also provides a simpler equivalent notation:

(list 1 2 3 4)

Lists can represent hierarchical structures with more than one dimension. This list, for example, is actually a tree:

(cons (list 1 2) (list 3 4))
=> '((1 2) 3 4)

((1 2) 3 4)
├── (1 2)
│   ├── 1
│   └── 2
├── 3
└── 4

We can now use lists as a conventional interface. They can express structured data and possess the closure property, so operations on them can still produce lists, which can be passed seamlessly into the next module. This makes it possible to construct programs by flexibly combining modules.

The book illustrates this with two programs: one computes the sum of the squares of the odd leaves in a tree; the other produces a list of even Fibonacci numbers:

(define (sum-odd-squares tree)
  (cond ((null? tree) 0)
	((not (pair? tree))
	 (if (odd? tree) (square tree) 0))
	(else (+ (sum-odd-squares
		  (car tree))
		 (sum-odd-squares
		  (cdr tree))))))

(define (even-fibs n)
  (define (next k)
    (if (> k n)
	nil
	(let ((f (fib k)))
	  (if (even? f)
	      (cons f (next (+ k 1)))
	      (next (+ k 1))))))
  (next 0))

At first glance, they do not appear to share an obvious structure. In fact, their information processing can follow similar patterns:

  • Enumerate all leaves → filter odd values → map to their squares → accumulate by summing.
  • Enumerate all integers → map to Fibonacci numbers → filter even values → accumulate by summing.

We can abstract these stages and use lists as the interface to construct more general programs.

The enumeration stage:

(define (enumerate-tree tree)
  (cond ((null? tree) nil)
	((not (pair? tree)) (list tree))
	(else (append (enumerate-tree (car tree))
		      (enumerate-tree (cdr tree))))))

(define (enumerate-interval low high)
  (if (> low high)
      nil
      (cons low
	    (enumerate-interval (+ low 1) high))))

The filtering stage:

(define (filter predicate sequence)
  (cond ((null? sequence) nil)
	((predicate (car sequence))
	 (cons (car sequence)
	       (filter predicate (cdr sequence))))
	(else  (filter predicate (cdr sequence)))))

Scheme already provides map, so we do not need to construct it ourselves.

The accumulation stage:

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
	  (accumulate op initial (cdr sequence)))))

The two programs constructed this way:

(define (sum-odd-squares tree)
  (accumulate
   +
   0
   (map square
	(filter odd?
		(enumerate-tree tree)))))

(define (even-fibs n)
  (accumulate
   cons
   nil
   (filter even?
	   (map fib
		(enumerate-interval 0 n)))))

Multiple Representations of Abstract Data

By designing constructors and selectors, we established an abstraction barrier that lets higher-level programs operate without knowing how the data is represented underneath. A system can, however, have more than one representation of the same abstract data type. Sometimes we need a system capable of handling several of them.

A typical example is complex numbers, which can be represented in rectangular or polar coordinates. The former stores the real and imaginary parts, while the latter stores magnitude and angle. With a rectangular representation, the constructors and selectors would look like this:

(define (make-from-real-imag x y) (cons x y))

(define (make-from-mag-ang r a)
  (cons (* r (cos a)) (* r (sin a))))

(define (real-part z) (car z))
(define (imag-part z) (cdr z))

(define (magnitude z)
  (sqrt (+ (square (real-part z))
	   (square (imag-part z)))))
(define (angle z)
  (atan (imag-part z) (real-part z)))

With a polar representation:

(define (make-from-mag-ang r a) (cons r a))
(define (make-from-real-imag x y)
  (cons (sqrt (+ (square x) (square y)))
	(atan y x)))

(define (magnitude z) (car z))
(define (angle z) (cdr z))

(define (real-part z)
  (* (magnitude z) (cos (angle z))))
(define (imag-part z)
  (* (magnitude z) (sin (angle z))))

How can both representations coexist in one system? The obvious approach is to attach a tag and use it to determine which representation the data uses:

(define (attach-tag type-tag contents)
  (cons type-tag contents))

(define (type-tag datum)
  (if (pair? datum)
      (car datum)
      (error "Bad tagged datum: TYPE-TAG" datum)))

(define (contents datum)
  (if (pair? datum)
      (cdr datum)
      (error "Bad tagged datum: CONTENTS" datum)))

We can then construct generic selectors:

(define (real-part z)
  (cond ((rectangular? z) (real-part-rectangular (contents z)))
	((polar? z) (real-part-polar (contents z)))
	(else (error "Unknown type:  REAL-PART" z))))
(define (imag-part z)
  (cond ((rectangular? z) (imag-part-rectangular (contents z)))
	((polar? z) (imag-part-polar (contents z)))
	(else (error "Unknown type: IMAG-PART" z))))
(define (magnitude z)
  (cond ((rectangular? z) (magnitude-rectangular (contents z)))
	((polar? z) (magnitude-polar (contents z)))
	(else (error "Unknown type: MAGNITUDE" z))))
(define (angle z)
  (cond ((rectangular? z) (angle-rectangular (contents z)))
	((polar? z) (angle-polar (contents z)))
	(else (error "Unknown type: ANGLE" z))))

This system has an obvious drawback: poor additivity. Whenever we introduce a new representation, we must modify all the existing constructors and selectors concerned with it.

A different approach, called data-directed programming, solves this problem. Each data type defines its own selectors, and a generic apply procedure chooses the appropriate selector for each representation. Naturally, the relationship between operations and representations takes the form of a table:

Operations Polar Rectangle
real-part real-part-polar real-part-rectangle
imag-part imag-part-polar imag-part-rectangle
magnitude magnitude-polar magnitude-rectangle
angle angle-polar angle-rectangle

Whenever we create a new representation, we simply insert its selectors into this table. The generic apply procedure automatically chooses the appropriate one:

(define (apply-generic op . args)
  (let ((type-tags (map type-tag args)))
    (let ((proc (get op type-tags)))
      (if proc
	  (apply proc (map contents args))
	  (error "No method for these types: APPLY-GENERIC"
	    (list op type-tags))))))

Another alternative to our initial tagged-data style is message passing. The former effectively reads the table row by row, while the latter reads it column by column. In this style, a constructor dispatches according to the requested selector rather than the data representation:

(define (make-from-real-imag x y)
  (define (dispatch op)
    (cond ((eq? op 'real-part) x)
	  ((eq? op 'imag-part) y)
	  ((eq? op 'magnitude) (sqrt (+ (square x) (square y))))
	  ((eq? op 'angle) (atan y x))
	  (else (error "Unknown op: MAKE-FROM-REAL-IMAG" op))))
  dispatch)

In short, attaching tags directly to abstract data gave us poor additivity: adding a representation required modifying existing procedures. Message passing does not eliminate that issue altogether; it transforms how we look at the table. The additivity problem then arises only when adding a new kind of selector, so it is encountered less often. Data-directed programming is a more comprehensive solution, using tag-based dispatch in the generic apply procedure to remove the additivity problem.