リスト構造を実装する二つの考え方がある. 第一は純粋に表現の論点で, 典型的な計算機メモリーの記憶場所とアドレス機能だけを使い, Lisp対の「箱とポインタ」をどう表現するかである. 第二の論点は, 計算の進行に伴うメモリーの管理に関するものである. Lispシステムの演算は実質的に新しいデータオブジェクトを作り出す能力に依存する. これには解釈中のLispの手続きが積極的に作り出したオブジェクトと, 解釈系が自分で作り出した, 環境や引数リストのような構造とがある. 高速にアクセス出来る無限のメモリーが計算機にあれば, 新しいデータオブジェクトが常に作り出されていても何の問題もないが,
計算機のメモリーは有限の大きさだけ使用可能である(残念なことだ). それ故Lispシステムは,
自動記憶割当て(automatic storage allocation)
機能を用意し, 無限メモリーの幻想を抱かせる. データオブジェクトが不要になった時, それに割り当てられていたメモリーは自動的に再生され, 新しいデータオブジェクトを構成するのに使われる. こういう自動記憶割当てを実現する方法はたくさんある. 本節で論じる方法はごみ集め(garbage
collection)という.