In section 5.4, we will show how to implement a Scheme evaluator as a
register machine. In order to simplify the discussion, we will assume that our
register machines can be equipped with a
list-structured memory, in
which the basic operations for manipulating list-structured data are primitive.
Postulating the existence of such a memory is a useful abstraction when one is
focusing on the mechanisms of control in a Scheme interpreter, but this does
not reflect a realistic view of the actual primitive data operations of
contemporary computers. To obtain a more complete picture of how a Lisp system
operates, we must investigate how list structure can be represented in a way
that is compatible with conventional computer memories.
在 5.4 节中，我们将展示如何将 Scheme 求值器实现为一台寄存器机器。为了简化讨论，我们将假设寄存器机器可以配备一种表结构内存 (list-structured memory)，其中操纵表结构数据的基本操作都是基本的。在专注于 Scheme 解释器的控制机制时，假定存在这样一种内存是一种有用的抽象，但这并不反映当代计算机实际基本数据操作的真实面貌。为了更完整地理解 Lisp 系统的运作方式，我们必须研究如何以与传统计算机内存兼容的方式表示表结构。
There are two considerations in implementing list structure. The first is
purely an issue of representation: how to represent the “box-and-pointer”
structure of Lisp pairs, using only the storage and addressing capabilities of
typical computer memories. The second issue concerns the management of memory
as a computation proceeds. The operation of a Lisp system depends crucially on
the ability to continually create new data objects. These include objects that
are explicitly created by the Lisp procedures being interpreted as well as
structures created by the interpreter itself, such as environments and argument
lists. Although the constant creation of new data objects would pose no
problem on a computer with an infinite amount of rapidly addressable memory,
computer memories are available only in finite sizes (more’s the pity). Lisp
systems thus provide an
automatic storage allocation facility to
support the illusion of an infinite memory. When a data object is no longer
needed, the memory allocated to it is automatically recycled and used to
construct new data objects. There are various techniques for providing such
automatic storage allocation. The method we shall discuss in this section is
called
garbage collection.
实现表结构涉及两方面的考量。第一方面纯粹是表示问题：如何仅用典型计算机内存的存储和寻址能力来表示 Lisp 序对的"盒子与指针"结构。第二方面涉及计算进行过程中的内存管理问题。Lisp 系统的运行关键依赖于持续创建新数据对象的能力，这些对象既包括被解释的 Lisp 过程显式创建的对象，也包括解释器自身创建的结构，如环境和参数表。尽管在具有无限容量且可快速寻址的内存的计算机上，不断创建新数据对象不成问题，但计算机内存的实际容量是有限的（实属遗憾）。因此，Lisp 系统提供了一种自动存储分配 (automatic storage allocation) 机制，以支持无限内存的假象。当某个数据对象不再需要时，分配给它的内存将被自动回收，用于构造新的数据对象。实现这种自动存储分配有多种技术，本节将讨论的方法称为垃圾收集。