data-structures - lisp 等链表的表示

Question

谁能概述一下 LISP 中的链表在计算机内存中是如何表示的？计算机是使用 cpu 寄存器来保存指针，还是使用堆来保存列表的头部和其余部分？

Answer 1

这在很大程度上取决于所使用的特定编译器和语言运行时。然而，一般来说，类 Lisp 语言中的数据结构是堆分配的单元格，带有指向其邻居的指针。然后，当函数对数据进行操作时，这些数据将加载到硬件寄存器中。

考虑 Haskell 中的链表类型:

 data [a] = [] | a : [a]

给定的列表可以写成:

1 : (2 : (3 : (4 : (5 : []))))

或更简洁:

[1,2,3,4,5]

这表示为以下形式的堆分配对象:

其中箭头代表指针； (:) 表示一个“cons cell”，一个存储指向当前元素的指针的小结构，以及列表的尾部。

现在，当一个函数访问这个数据结构时，它会将指向该结构的指针加载到寄存器中，并开始从这些指针加载数据。其中的精确细节取决于编译模型和运行时系统模型。例如。对于 GHC Haskell，这是由 STG Machine 给出的.此外，指针中的低端位可用于指示所指向的特定构造函数；它的评估状态(已评估或未评估)，如果它很小，甚至是值本身(这是 pointer tagging optimization )。