3.3.3 Representing Tables

When we studied various ways of representing sets in Chapter 2, we

mentioned in 2.3.3 the task of maintaining a table of records

indexed by identifying keys. In the implementation of data-directed

programming in 2.4.3, we made extensive use of two-dimensional

tables, in which information is stored and retrieved using two keys. Here we

see how to build tables as mutable list structures.

在第 2 章研究集合的各种表示方式时，我们在 2.3.3 节提到了维护一张以标识键（key）为索引的记录表的任务。在 2.4.3 节实现数据导向编程时，我们大量使用了二维表，其中的信息通过两个键来存储和检索。本节将介绍如何将表构建为可变的表结构。

We first consider a one-dimensional table, in which each value is stored under

a single key. We implement the table as a list of records, each of which is

implemented as a pair consisting of a key and the associated value. The records

are glued together to form a list by pairs whose cars point to

successive records. These gluing pairs are called the

backbone of

the table. In order to have a place that we can change when we add a new

record to the table, we build the table as a

headed list. A headed

list has a special backbone pair at the beginning, which holds a dummy

“record”—in this case the arbitrarily chosen symbol *table*.

Figure 3.22 shows the box-and-pointer diagram for the table

我们首先考虑一维表——其中每个值都存储在单个键之下。我们将表实现为一个记录的表，其中每条记录实现为一个由键和对应值组成的序对。各条记录通过 car 依次指向下一条记录的序对串联在一起，形成一张表。这些起串联作用的序对被称为表的骨干（backbone）。为了在向表中添加新记录时有一个固定的位置可以修改，我们将表构建为一张带表头的表（headed list）。带表头的表在最前面有一个特殊的骨干序对，它持有一条虚设的“记录”——在这里是任意选定的符号 *table*。图 3.22 展示了该表的盒-指针图。

Figure 3.22: A table represented as a headed list.

图 3.22：用带表头的表表示的表。

To extract information from a table we use the lookup procedure, which

takes a key as argument and returns the associated value (or false if there is

no value stored under that key). Lookup is defined in terms of the

assoc operation, which expects a key and a list of records as arguments.

Note that assoc never sees the dummy record. Assoc returns the

record that has the given key as its car. Lookup then checks to see that the resulting record

returned by assoc is not false, and returns the value (the cdr)

of the record.

要从表中提取信息，我们使用过程 lookup，它以一个键为参数，返回与之关联的值（若该键下没有存储任何值则返回 false）。lookup 是借助 assoc 操作来定义的，assoc 以一个键和一张记录表为参数。注意，assoc 永远不会看到虚设记录。assoc 返回以给定键为 car 的那条记录；lookup 随后检查 assoc 返回的记录是否不为 false，并返回该记录的值（即 cdr）。

To insert a value in a table under a specified key, we first use assoc

to see if there is already a record in the table with this key. If not, we

form a new record by consing the key with the value, and insert this at

the head of the table’s list of records, after the dummy record. If there

already is a record with this key, we set the cdr of this record to the

designated new value. The header of the table provides us with a fixed

location to modify in order to insert the new record.

要在表中给定键下插入一个值，我们首先用 assoc 检查表中是否已有以该键为索引的记录。若没有，则用 cons 将键与值组合成一条新记录，并将其插入表的记录表的表头——即紧接在虚设记录之后。若已有以该键为索引的记录，则将该记录的 cdr 设置为指定的新值。表头为我们提供了插入新记录时可以修改的固定位置。

To construct a new table, we simply create a list containing the symbol

*table*:

构造一张新表时，只需创建一个包含符号 *table* 的表：

Subheading: Two-dimensional tables

子标题：二维表

In a two-dimensional table, each value is indexed by two keys. We can

construct such a table as a one-dimensional table in which each key identifies

a subtable. Figure 3.23 shows the box-and-pointer diagram for the table

在二维表中，每个值由两个键共同索引。我们可以将这样的表构造为一张一维表，其中每个键标识一张子表（subtable）。图 3.23 展示了该表的盒-指针图，

which has two subtables. (The subtables don’t need a special header symbol,

since the key that identifies the subtable serves this purpose.)

Figure 3.23: A two-dimensional table.

它包含两张子表。（子表不需要特殊的表头符号，因为标识该子表的键本身就起到了这个作用。）图 3.23：一张二维表。

When we look up an item, we use the first key to identify the correct subtable.

Then we use the second key to identify the record within the subtable.

在查找某个条目时，我们用第一个键确定正确的子表，再用第二个键在子表中定位相应的记录。

To insert a new item under a pair of keys, we use assoc to see if there

is a subtable stored under the first key. If not, we build a new subtable

containing the single record (key-2, value) and insert it into

the table under the first key. If a subtable already exists for the first key,

we insert the new record into this subtable, using the insertion method for

one-dimensional tables described above:

要在一对键之下插入一个新条目，我们先用 assoc 检查第一个键下是否已存储了子表。若没有，则构建一张仅含记录 (key-2, value) 的新子表，并将其以第一个键为索引插入主表。若第一个键下已存在子表，则使用上文描述的一维表插入方法将新记录插入该子表：

Subheading: Creating local tables

子标题：创建局部表

The lookup and insert! operations defined above take the table as
an argument. This enables us to use programs that access more than one table.
Another way to deal with multiple tables is to have separate lookup and
insert! procedures for each table. We can do this by representing a
table procedurally, as an object that maintains an internal table as part of
its local state. When sent an appropriate message, this “table object”
supplies the procedure with which to operate on the internal table. Here is a
generator for two-dimensional tables represented in this fashion:

Using make-table, we could implement the get and put
operations used in 2.4.3 for data-directed programming, as
follows:

Get takes as arguments two keys, and put takes as arguments two
keys and a value. Both operations access the same local table, which is
encapsulated within the object created by the call to make-table.