c - 缺点/对的实施

Question

用 C 等低级语言实现 Lisp 的 cons/pair 有哪些选择？

一种常见的实现是由字段type、car和cdr组成的结构。我知道链表在存储方面效率不高，但是额外的类型字段使情况变得更糟。

我在 Wikipedia 上读到Lisp 机器过去常常为每个单词添加额外的位以获取类型信息。但是今天的架构（x86、ARM）有哪些选择呢？

Answer 1

Cons cells are just one type of data we need to represent in Lisp. Others are arrays or vectors. Strings. Characters. Numbers. Symbols. Records. Instances of Classes.

Not only Lisp Machines used tag bits. Most Lisp implementations use them.

Most Lisp implementations use just the bits inside each memory word. Various Lisp Machines differed in their number of bits per word. Symbolics 36** machines used 36 bit words. Symbolics Ivory used 40 bit words. TI Explorer used 32bit words. So Symbolics used an unusual word size and TI used a normal word size. Symbolics was able to address more memory with its 40bit CPUs - 16 GBytes. 8bits of a word were used for the tags. Symbolics also had various other optimizations in representing data (for example lists could be represented as cdr-coded vectors - this technique is not used in current Lisp implementations).

Most of today's CPUs are 32bit or 64bit architectures. That makes a Lisp cons cell then two of these words in size and the bits have to fit into these word sizes. A fixnum is smaller than 32bit or 64bit. A fixnum is an integer which fits into a word minus the tag bits. For larger integers the numbers need to be represented differently. Thus a full 64bit long number is not representable as a fixnum on an 64bit machine. Common Lisp provides information about these sizes. On my 64bit LispWorks the most positive fixnum is 1152921504606846975.

CL-USER > MOST-POSITIVE-FIXNUM
1152921504606846975

It would be unusual to waste extra memory for the tag bits. Most current Lisp implementations have to put the tag bits into the data word (32bit or 64bit). Lisp implementors have been working hard to make this as efficient as possible.

Answer 2

您可以用指针type中的标记替换该字段。

结合NaN 装箱，您可以将每个堆栈槽（以及结构的carandcdr字段cons）减少到double.

malloc但是，对于每个 cons 单元格，您仍然会有开销（一个或两个单词）。