As we have seen, pairs provide a primitive glue that we can
use to construct compound data objects.
shows a standard way to visualize a
pair—in this case, the pair formed by
In this representation, which is called
notation, each compound object is shown as a
pointer to a box. The box for a pair
has two parts, the left part containing the head of the pair and the
right part containing the tail.
We have already seen that
can be used to combine not only numbers but pairs as well. (You made use
of this fact, or should have, in doing
and 2.3.) As a consequence, pairs provide
a universal building block from which we can construct all sorts of data
shows two ways to use pairs to combine the numbers 1, 2, 3, and 4.
The ability to create pairs whose elements are pairs is the essence of
list structure's importance as a representational tool. We refer to
this ability as the
closure property of
In general, an operation for combining data objects satisfies the closure
property if the results of combining things with that operation can
themselves be combined using the same operation.
Closure is the key to power in any means of combination because it permits
us to create
hierarchical structures—structures made up of parts, which
themselves are made up of parts, and so on.
From the outset of chapter 1, we've made essential use of
closure in dealing with
because all but the very simplest programs rely on the fact that the
elements of a combination can themselves be combinations. In this section,
we take up the consequences of closure for compound data. We describe some
conventional techniques for using pairs to represent sequences and trees,
and we exhibit a graphics language that illustrates closure in a vivid
we choose to draw primitive objects directly inside of the boxes of the
pairs that contain them, in an attempt to be consistent with a similar
practice introduced in
section 3.2. The box-and-pointer
diagrams in the original version of the textbook include separate boxes
for primitive objects, such as 1 and 2, each containing a
representation of the object.
The use of the
closure here comes from abstract algebra, where a set of
elements is said to be closed under an operation if applying the operation
to elements in the set produces an element that is again an element of the
set. The Lisp community also (unfortunately) uses the word
closure to describe a totally unrelated concept: A closure
is an implementation technique for representing
functions with free names.
We do not use the word closure in this second sense in this
The notion that a means of
combination should satisfy closure is a straightforward idea. Unfortunately,
the data combiners provided in many popular programming languages do not
satisfy closure, or make closure cumbersome to exploit. In
Basic, one typically combines data elements by assembling them into
arrays—but one cannot form arrays whose elements are themselves
C admit structures whose elements are structures. However, this requires
that the programmer manipulate pointers explicitly, and adhere to the
restriction that each field of a structure can contain only elements of a
prespecified form. Unlike Lisp with its pairs, these languages have no
built-in general-purpose glue that makes it easy to manipulate compound
data in a uniform way. This limitation lies behind Alan
Perlis's comment in his foreword to this book: In Pascal the
plethora of declarable data structures induces a specialization within
functions that inhibits and penalizes casual cooperation. It is better to
have 100 functions operate on one data structure than to have 10 functions
operate on 10 data structures.