在lisp中表示鏈接列表

Question

任何人都可以概述如何在LISP中鏈接列表在計算機的內存中表示嗎？計算機是否利用cpu寄存器來保存指針頭部和列表的其餘部分，或者是堆的用途？

Answer 1

這在很大程度上取決於所使用的特定編譯器和語言運行庫。但是，通常Lisp-like語言中的數據結構是指向其鄰居的堆分配單元。然後，當函數對數據進行操作時，這些數據會被載入硬件寄存器。

考慮在Haskell鏈表類型：

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

一個給定的列表可能被寫爲：

1：（2：（3：（4：（5：[]））） ）

或更簡明：

[1,2,3,4,5]

這被表示爲一個堆的alloc形式的ated對象：

其中箭頭表示的指針;並且(:)代表「cons小區」，存儲指向當前元素的指針的小結構以及列表的尾部。

現在，當一個函數訪問這種數據結構，它會加載指針結構到寄存器，並從這些指針開始加載數據。其具體細節取決於編譯模型和運行時系統模型。例如。對於GHC Haskell，這由STG Machine給出。另外，指針中的低端位可以用來指示指向的特定構造函數;其評估狀態（評估或未評估），甚至是價值本身（如果它很小）（這是pointer tagging optimization）。

Answer 2

取決於。如果你有一個真正的問題，Stackoverflow是最好的。

「LISP」是大型語言系列和數百種不同的實現。

已經嘗試了各種實現鏈表的方法。

有一些關於Lisp實現的書籍，有許多小型和大型的開源Lisp實現可供學習。

相關文獻例如可以在這裏找到：http://library.readscheme.org/page8.html

Answer 3

有關Lisp的，最鼓舞人心的來源之一這樣的哲學問題是Anatomy of Lisp。即使現在有點過時了。閱讀它（很多年前）對我來說是一個啓發，不僅關於Lisp，還關於一般編程。另一本關於Lisp實現的優秀書是Lisp in Small Pieces。如果你認真學習Lisp內部知識，這兩個將會幫助你很多。