2.3.6 Cons Cell and List Types

コンスセル(cons cell)は、CARスロット、CDRスロットと呼ばれる2つのスロットから構成されるオブジェクトです。各スロットは、任意のLispオブジェクトを保持できます。そのときCARスロットに保持されるオブジェクトが何であれ、わたしたちは“このコンスセルのCAR”のような言い方をします。これはCDRの場合も同様です。

リスト(list)は、コンスセルの連続するシリーズで、各コンスセルのCDRスロットは、次のコンスセル、または空リストを保持します。空リストは実際にはシンボルnilです。詳細については、Listsを参照してください。ほとんどのコンスセルはリストの一部として使用されるので、わたしたちはコンスセルにより構成される任意の構造を、リスト構造(list structure)という用語で参照します。

Cプログラマーにたいする注意: Lispのリストはコンスセルにより構築される、リンクリスト(linked list)として機能します。Lispではポインターは暗黙的なので、わたしたちはコンスセルのスロットが、値を“保持(hold)”するのか、それとも値を“指す(point)”のかを区別しません。

コンスセルはLispの中心なので、“コンスセルではないオブジェクト”にたいする単語もあります。これらのオブジェクトはアトム(atoms)と呼ばれます。

リストにたいする入力構文とプリント表現は等しく、それは左カッコ、任意の数の要素、右カコから構成されます。以下はリストの例です:

(A 2 "A")            ; 3要素のリスト。
()                   ; 要素がないリスト(空リスト)。
nil                  ; 要素がないリスト(空リスト)。
("A ()")             ; 1要素のリスト: 文字列"A ()"。
(A ())               ; 2要素のリスト: Aと空リスト。
(A nil)              ; 同上
((A B C))            ; 1要素のリスト
                     ;   (この要素は、3要素のリスト)。

読み取りにおいては、カッコの内側は、リストの要素になります。つまり、コンスセルは各要素から作成されます。コンスセルのCARスロットは要素を保持し、CDRスロットはリスト内の次のコンスセル(このコンスセルはリスト内の次の要素を保持します)を参照します。最後のコンスセルのCDRスロットは、nilを保持するようにセットされます。

CAR、CDRという名称は、Lispの歴史に由来します。オリジナルのLisp実装はIBM 704コンピューターで実行されていました。ワードを2つの部分、つまり“address”と呼ばれる部分と、“decrement”と呼ばれる部分に分割していて、その際CARはaddress部から内容を取り出す命令で、CDRはdecrement部から内容を取り出す命令でした。対照的に“cons cells”は、これらを作成する関数consから命名されました。この関数は関数の目的、すなわちセルを作る(construction of cells)という目的から命名されました。