灯下 登录
计算机科学 / SICP / section 中英对照

2.2 Hierarchical Data and the Closure Property

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 章一开始,我们在处理过程时就已大量运用了闭包,因为除最简单的程序外,几乎所有程序都依赖于"组合式的元素本身也可以是组合式"这一事实。在本节中,我们来探讨闭包对复合数据的影响。我们将介绍一些用序对表示序列和树的惯用技术,并展示一种以生动方式阐明闭包的图形语言。