在 Lisp 中列表結(jié)構(gòu)是一種常用數(shù)據(jù)結(jié)構(gòu)非剃，它的基礎(chǔ)是序?qū)φ八蹋瑫r序?qū)σ彩呛芏鄶?shù)據(jù)對象的基礎(chǔ)結(jié)構(gòu)霜威，為了揭示列表結(jié)構(gòu)的數(shù)據(jù)操作在計算機中的細節(jié)胆剧，我們需要研究在現(xiàn)代計算機存儲器中如何實現(xiàn)列表結(jié)構(gòu)及其操作。
將存儲看作向量
常規(guī)計算機的存儲器通骋Ｂ疲可以視作一組連續(xù)的存儲單元卫袒，而且每個存儲單元都有一個獨一無二的 地址（address）。一組連續(xù)的存儲信息可以通過基準(zhǔn)存儲地址與偏移量的加法運算得出单匣，所以這種存儲方式并不會由于連續(xù)存儲信息的增長而增加獲取指定地址內(nèi)存儲信息的消耗時間夕凝。根據(jù)這種概念，我們可以將計算機存儲器映射為數(shù)據(jù)結(jié)構(gòu) 向量（vector）户秤，向量中的每個元素都可以通過索引訪問码秉，于是通過下列 Scheme 基礎(chǔ)程式便可以操作向量。
(vector-ref <vector> <n>) ; 將返回向量的第 n 個元素
(vector-set! <vector <n> <value>) ; 將向量的第 n 個元素設(shè)置為指定值
各種數(shù)據(jù)在向量概念上的實現(xiàn)
我們可以將計算機存儲器看作兩個獨立的向量 the-cars 和 the-cdrs 鸡号。分別存儲 car 和 cdr 的數(shù)據(jù)转砖，而 car 和 cdr 中保存的只是對應(yīng)的向量索引的指針。除了序?qū)χ饩ò椋琇isp 還需要存儲其他類型的數(shù)據(jù)府蔗。為了區(qū)分不同類型的指針會附帶類型信息，這種指針也稱為 類型指針（typed pointer）汞窗。例如姓赤，數(shù)字 4 的指針為 n4，其中 n 表示該指針類型是數(shù)字仲吏；存儲在向量索引為 4 的序?qū)χ羔槥?p4不铆，其中 p 表示該指針類型為序?qū)Α?/p>
除了上述情況外標(biāo)識數(shù)據(jù)會比較特別蝌焚，Lisp 在生成標(biāo)識前會先讀取標(biāo)識字符序列，然后在 對象表（obarray） 中查找該標(biāo)識是否已經(jīng)存在（也就是已經(jīng)存在對應(yīng)的指針）誓斥，如果已經(jīng)存在則返回該指針只洒，如果不存在則需要生成新的標(biāo)識并保存在對象表中。
列表基礎(chǔ)操作
現(xiàn)在我們可以將列表基礎(chǔ)操作轉(zhuǎn)換為寄存器機器指令劳坑，具體實現(xiàn)如下毕谴。
(assign <reg1> (op vector-ref) (reg the-cars) (reg <reg2>)) ; implementation of (assign <reg1> (op car) (reg <reg2>))
(assign <reg1> (op vector-ref) (reg the-cdrs) (reg <reg2>)) ; implementation of (assign <reg1> (op cdr) (reg <reg2>))
(perform
(op vector-set!) (reg the-cars) (reg <reg1>) (reg <reg2>)) ; implemetation of (perform (op set-car!) (reg <reg1>) (reg <reg 2>))
(perform
(op vector-set!) (reg the-cdrs) (reg <reg1>) (reg <reg2>)) ; implementation of (perform (op set-cdr!) (reg <reg1>) (reg <reg2>))
;;; implementation of (assign <reg1> (op cons) (reg <reg2>) (reg <reg3>))
(perform
(op vector-set!) (reg the-cars) (reg free) (reg <reg2>))
(perform
(op vector-set!) (reg the-cdrs) (reg free) (reg <reg3>))
(assign <reg1> (reg free))
(assign free (op +) (reg free) (const 1))
其中 free 寄存器持有指向下一可用存儲單元的索引。
堆椗堇基礎(chǔ)操作
因為堆棧也是在列表的基礎(chǔ)上實現(xiàn)的析珊，所以它的相關(guān)指令也可以通過向量指令實現(xiàn)羡鸥。
(assign the-stack (op cons) (reg <reg>) (reg the-stack))) ; implementation of (save <reg>)
;;; implementation of (restore <reg>)
(assign <reg> (op car) (reg the-stack))
(assign the-stack (op cdr) (reg the-stack))
存儲的垃圾回收
由于實際情況中計算機的存儲大小有限蔑穴，為了使存儲器能夠不斷運行，我們需要對其中不再被使用的數(shù)據(jù)進行清除惧浴，這個過程稱為垃圾回收存和，此處我們應(yīng)用的垃圾回收方案為 停止并拷貝（stop-and-copy）。
停止并拷貝方案將存儲空間分為兩半衷旅，一半為工作空間捐腿，另一半為空閑空間。當(dāng)工作空間被填滿時柿顶，工作空間中有用的數(shù)據(jù)將被拷貝到空閑空間中茄袖，在拷貝完成后此時工作空間中的剩余數(shù)據(jù)都是無用數(shù)據(jù)，隨后空閑空間與工作空間的角色發(fā)生轉(zhuǎn)換嘁锯。
其中識別有用的數(shù)據(jù)可以通過當(dāng)前所有寄存器中存儲的指針指向的數(shù)據(jù)為有用的數(shù)據(jù)宪祥，其次這些數(shù)據(jù)經(jīng)過不斷 car 和 cdr 能夠訪問的數(shù)據(jù)也是有用的數(shù)據(jù)。
