cons/结对的实现

Question

在低级语言(如C )中实现Lisp的缺点/对的选项有哪些？

一个常见的实现是由字段类型、car和cdr组成的结构。我知道链接列表对于存储不是很有效，但是附加的类型文件使它更加糟糕。

我在维基百科上读到，Lisp机过去常常在每个单词中添加额外的位来表示类型信息。但是现在的体系结构(x86，ARM)有哪些选择呢？

Answer 1

Cons单元格只是我们需要在Lisp中表示的一种数据类型。另一些则是数组或向量。弦乐。人物。数字。符号。记录。类的实例。

不仅Lisp机器使用标记位。大多数Lisp实现都使用它们。

大多数Lisp实现只使用每个内存字中的位。不同的Lisp机器每个字的位数不同。符号36**机器使用36位单词。象牙人用了40个字。TI资源管理器使用了32位的单词。所以Symbolics使用了一个不寻常的单词大小，TI使用了一个正常的单词大小。Symbolics能够用它的40位CPUs 16 GBytes来解决更多的内存问题。标记用一个单词的8位。Symbolics在表示数据时还进行了其他各种优化(例如，列表可以表示为cdr编码的向量--这种技术在当前的Lisp实现中没有使用)。

当今大多数CPU都是32位或64位架构。这就产生了一个单元格，然后其中两个字的大小和位必须符合这些字的大小。固定位小于32位或64位。fixnum是一个整数，它适合于一个单词减去标记位。对于较大的整数，需要以不同的方式表示数字。因此，一个完整的64位长的数字不能表示为固定在64位机器上。通用Lisp提供了有关这些大小的信息。在我的64位LispWorks上，最正面的固定值是1152921504606846975。

CL-USER > MOST-POSITIVE-FIXNUM
1152921504606846975

将额外的内存浪费在标记位上是不寻常的。大多数当前的Lisp实现都必须将标记位放入数据字(32位或64位)。Lisp实现者一直在努力工作，以尽可能提高效率。

Answer 2

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

结合NaN拳击，您可以将每个堆栈槽(以及cons结构的car和cdr字段)缩小到double大小。

但是，对于每个cons单元格，仍然有malloc开销(一个或两个单词)。