2.4.6 コンスセルとリスト型

コンスセル(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)という目的から命名されました。