コンスセル(cons cell)はCARスロット、CDRスロットと呼ばれる2つのスロットから構成されるオブジェクトです。それぞれのスロットはには、任意のLispオブジェクトを保持できます。そのときCARスロットに保持されるオブジェクトが何であれ、わたしたちは“このコンスセルのCAR”のような言い方をします。これはCDRの場合も同様です。
リスト(list)はコンスセルの連続するシリーズで、各コンスセルのCDRスロットは次のコンスセル、または空リストを保持します。空リストは実際にはシンボルnilです。詳細については、リストを参照してください。ほとんどのコンスセルはリストの一部として使用されるので、わたしたちはコンスセルにより構成される任意の構造を、リスト構造(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)という目的から命名されました。