Abstraction

We've really been talking about abstraction all along. Whenever you find yourself performing several similar computations, such as

> (sentence 'she (word 'run 's))
(SHE RUNS)

> (sentence 'she (word 'walk 's))
(SHE WALKS)

> (sentence 'she (word 'program 's))
(SHE PROGRAMS)

and you capture the similarity in a procedure

(define (third-person verb)
  (sentence 'she (word verb 's)))

you're abstracting the pattern of the computation by expressing it in a form that leaves out the particular verb in any one instance.

In the preface we said that our approach to computer science is to teach you to think in larger chunks, so that you can fit larger problems in your mind at once; "abstraction" is the technical name for that chunking process.

In this part of the book we take a closer look at two specific kinds of abstraction. One is data abstraction, which means the invention of new data types. The other is the implementation of higher-order functions, an important category of the same process abstraction of which third-person is a trivial example.

Until now we've used words and sentences as though they were part of the natural order of things. Now we'll discover that Scheme sentences exist only in our minds and take shape through the use of constructors and selectors (sentence, first, and so on) that we wrote. The implementation of sentences is based on a more fundamental data type called lists. Then we'll see how lists can be used to invent another in-our-minds data type, trees. (The technical term for an invented data type is an abstract data type.)

You already know how higher-order functions can express many computational processes in a very compact form. Now we focus our attention on the higher-order procedures that implement those functions, exploring the mechanics by which we create these process abstractions.