As we have seen, pairs provide a primitive “glue” that we can use to
construct compound data objects. Figure 2.2 shows a standard way to
visualize a pair—in this case, the pair formed by (cons 1 2). In this
representation, which is called
box-and-pointer notation, each object
is shown as a
pointer to a box. The box for a primitive object
contains a representation of the object. For example, the box for a number
contains a numeral. The box for a pair is actually a double box, the left part
containing (a pointer to) the car of the pair and the right part
containing the cdr.
Figure 2.2: Box-and-pointer representation of (cons 1 2).
正如我们所见,序对提供了一种基本的"粘合剂",可用于构造复合数据对象。图 2.2 展示了可视化序对的一种标准方式——以 `(cons 1 2)` 构成的序对为例。在这种称为盒指针表示法 (box-and-pointer notation) 的表示中,每个对象显示为指向一个盒子的指针。基本对象的盒子中包含该对象的表示,例如数的盒子中包含一个数字字符。序对的盒子实际上是一个双格盒子:左格包含该序对 car 的(指针),右格包含 cdr。
图 2.2:`(cons 1 2)` 的盒指针表示。
We have already seen that cons can be used to combine not only numbers
but pairs as well. (You made use of this fact, or should have, in doing
Exercise 2.2 and Exercise 2.3.) As a consequence, pairs provide a
universal building block from which we can construct all sorts of data
structures. Figure 2.3 shows two ways to use pairs to combine the
numbers 1, 2, 3, and 4.
Figure 2.3: Two ways to combine 1, 2, 3, and 4 using pairs.
我们已经看到,`cons` 不仅可以组合数,也可以组合序对。(在做练习 2.2 和练习 2.3 时,你应当已经用到了这一事实。)因此,序对提供了一种通用的构造块,可以用来构造各种各样的数据结构。图 2.3 展示了用序对组合数 1、2、3、4 的两种方式。
图 2.3:用序对组合 1、2、3、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 cons. 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
能够创建以序对为元素的序对,正是表结构作为表示工具之重要性的本质所在。我们将这种能力称为 `cons` 的闭包性质 (closure property)。一般而言,若将某种操作组合数据对象所得到的结果,还能用同一操作继续组合,则称该操作满足闭包性质。闭包是任何组合方法的强大之源,因为它使我们能够构造
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 procedures, 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 way.
从第 1 章一开始,我们在处理过程时就已大量运用了闭包,因为除最简单的程序外,几乎所有程序都依赖于"组合式的元素本身也可以是组合式"这一事实。在本节中,我们来探讨闭包对复合数据的影响。我们将介绍一些用序对表示序列和树的惯用技术,并展示一种以生动方式阐明闭包的图形语言。