谁能概述一下 LISP 中的链表是如何在计算机内存中表示的？计算机是使用 cpu 寄存器来保存列表的头部和其余部分的指针，还是使用堆？
问问题
1684 次
3 回答
4
这在很大程度上取决于所使用的特定编译器和语言运行时。然而，在类 Lisp 语言中，一般的数据结构是堆分配的单元，带有指向其邻居的指针。然后，当函数对数据进行操作时，它们会被加载到硬件寄存器中。
考虑 Haskell 中的链表类型：
data [a] = [] | a : [a]
给定的列表可以写成：
1：（2：（3：（4：（5：[]））））
或更简洁地说：
[1,2,3,4,5]
这表示为以下形式的堆分配对象：
其中箭头代表指针；并(:)表示一个“cons cell”，一个存储指向当前元素的指针的小结构，以及列表的尾部。
现在，当一个函数访问这个数据结构时，它会将指向该结构的指针加载到寄存器中，并开始从这些指针中加载数据。其中的精确细节取决于编译模型和运行时系统模型。例如，对于 GHC Haskell，这是由STG Machine给出的。此外，指针中的低端位可用于指示所指向的特定构造函数；它的评估状态（已评估或未评估），如果它很小，甚至是值本身（这是指针标记优化）。
于 2012-06-06T12:41:48.090 回答
3
For such philosophical questions about Lisp, one of the most inspiring source is Anatomy of Lisp. Even if it is a bit dated now. Reading it (well, many years ago) was an enlightenment for me, not only about Lisp but about programming in general. Another excellent book about Lisp implementation is Lisp in Small Pieces. If you are serious about learning Lisp internals, these two will help you a lot.
于 2012-06-07T06:43:40.143 回答
2
要看。如果您遇到真正的问题，最好使用 Stackoverflow。
“LISP”是一大类语言和数百种不同的实现。
各种实现链表的方式都已经尝试过了。
有关于 Lisp 实现的书籍，还有很多大大小小的开源 Lisp 实现需要研究。
相关文献可以在这里找到，例如：http: //library.readscheme.org/page8.html
于 2012-06-06T10:48:48.043 回答